Bitscore

The scientists at UniBuc have recently discovered an ancient game played by the Dacians called Bitscore. They would write on a piece of paper multiple strictly positive numbers and the players had to choose subsets with the property that the number of digits in the binary form of the numbers create a strictly decreasing sequence. For instance $100, 63, 4, 2, 1$ is a valid sequence, while $100, 64$ is not valid.

Given an array of $N$ numbers compute the number of valid subsets. Because the result can be very big, print the result modulo $1 \ 000 \ 000 \ 007$.

$ATTENTION!$ The elements of a subset can be rearranged.

Input data

The first line contains a single number $N$ ($1 \le N \le 100 \ 000$). The second line contains $N$ numbers $\le 10^9$ separated with spaces.

Output data

The only line contains the number of valid subsets.

Constraints and clarifications

• For $35$ points, it is guaranteed that $N \leq 15$;
• For the last 65 points, we have $N \leq 100 \ 000$.

Example 1

stdin

6
1 3 2 16 5 9

stdout

47

Example 2

stdin

6
1 6 3 4 5 2

stdout

23

Explanation

For the second example the subsets are: $[(1)$, $(2)$, $(3)$, $(4)$, $(5)$, $(6)$, $(2, 1)$, $(3, 1)$, $(4, 1)$, $(4, 2)$, $(4, 3)$, $(5, 1)$, $(5, 2)$, $(5, 3)$, $(6, 1)$, $(6, 2)$, $(6, 3)$, $(4, 2, 1)$, $(4, 3, 1)$, $(5, 2, 1)$, $(5, 3, 1)$, $(6, 2, 1)$, $(6, 3, 1)]$