N. Bitscore
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$1000000007$$$.

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

Input

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

Output

The only line contains the number of valid subsets.

Scoring
  • for 35 points, it is guaranteed that $$$N \leq 15$$$
  • for the last 65 points, we have $$$N \leq 100000$$$
Examples
Input
6
1 3 2 16 5 9
Output
47
Input
6
1 6 3 4 5 2
Output
23
Note

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)]$$$