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

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Bit manipulation

Combinatorics


Solutions:
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))

def zeta_super(val, 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)