Jzzhu and Numbers

给出一个长度为 $n$ 的序列 $a_1,a_2, \cdots, a_n$。求构造出一个序列 $i_1 < i_2 < ... < i_k(1\le{k}\le{n})$ 使得 $a_{i_1}\&a_{i_2}\&\cdots \&a_{i_k}=0$（其中 $\&$ 表示按位与）的方案数模 $10^9+7$ 。 也就是从 $\{a_i\}$ 里面选出一个非空子集使这些数按位与起来为 $0$。 感谢@租酥雨 提供的翻译

Jzzhu have $ n $ non-negative integers $ a_{1},a_{2},...,a_{n} $ . We will call a sequence of indexes $ i_{1},i_{2},...,i_{k} $ $ (1<=i_{1}<i_{2}<...<i_{k}<=n) $ a group of size $ k $ . Jzzhu wonders, how many groups exists such that $ a_{i1} $ & $ a_{i2} $ & ... & $ a_{ik}=0 $ $ (1<=k<=n) $ ? Help him and print this number modulo $ 1000000007 $ $ (10^{9}+7) $ . Operation $ x $ & $ y $ denotes bitwise AND operation of two numbers.

The first line contains a single integer $ n $ $ (1<=n<=10^{6}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (0<=a_{i}<=10^{6}) $ .

Output a single integer representing the number of required groups modulo $ 1000000007 $ $ (10^{9}+7) $ .

3
2 3 3

0

4
0 1 2 3

10

6
5 2 0 5 2 1

53