410285: GYM103999 N 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 $$$1000000007$$$.

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

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.

The only line contains the number of valid subsets.

• for 35 points, it is guaranteed that $$$N \leq 15$$$
• for the last 65 points, we have $$$N \leq 100000$$$

6
1 3 2 16 5 9

47

6
1 6 3 4 5 2

23

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