449_D. Jzzhu and Numbers
Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k. 

Jzzhu wonders, how many groups exists such that ai1 & ai2 & ... & aik = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (109 + 7). Operation x & y denotes bitwise AND operation of two numbers.

Input

The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

Output a single integer representing the number of required groups modulo 1000000007 (109 + 7).

Examples

Input

3
2 3 3


Output

0


Input

4
0 1 2 3


Output

10


Input

6
5 2 0 5 2 1


Output

53
```python
import sys
input = lambda : sys.stdin.readline().rstrip()


sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))


# zeta mebius
def zeta_super(val, n):
    # len(val)==2^n
    out = val[:]
    for i in range(n):
        for j in range(1<<n):
            if not j>>i&1:
                out[j] += out[j^(1<<i)]
    return out

n = int(input())
a = list(map(int, input().split()))
m = max(a).bit_length()
M = 10**9+7
v = [0]*(1<<m)
for item in a:
    v[item] += 1
v2 = [1]
for i in range(n+1):
    v2.append(v2[-1]*2%M)
nv = zeta_super(v, m)
ans = 0
for b in range(1<<m):
    ans += (v2[nv[b]]-1)*pow(-1, bin(b).count("1"))
    ans %= M
print(ans%M)
```