A9485. Jzzhu and Numbers

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