Problem: Zero AND Subsets

Given a multiset of nonnegative integers a_1, a_2, .., a_N.

How many non-empty subsets of this set have a value bitwiseAND of 0?

Find the remainder of the answer divided by 10 ^ 9 + 7.

input


N
a_1 a_2 ... a_N


output

Divide the answer by 10 ^ 9 + 7 and output the remainder.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 0 \ leq a_i \ leq 2 ^ {20} -1



Input example


6
8 6 9 1 2 1


Output example


51






Example

Input

6
8 6 9 1 2 1


Output

51

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
#define MOD 1000000007
int main() {
	int n = ri();
	int a[n];
	for (auto &i : a) i = ri();
	
	std::vector<int> cnt(1 << 20);
	for (auto i : a) cnt[i]++;
	
	for(int i = 0; i < 20; i++)
		for(int j = 0; j < 1 << 20; j++) if (!(j >> i & 1)) cnt[j] += cnt[j | 1 << i];
	
	int beki2[n + 1];
	beki2[0] = 1;
	for (int i = 1; i <= n; i++) beki2[i] = beki2[i - 1] * 2 % MOD;
	
	int all = 0;
	for (int i = 0; i < 1 << 20; i++) {
		if (__builtin_popcount(i) & 1) all -= beki2[cnt[i]];
		else all += beki2[cnt[i]];
		if (all < 0) all += MOD;
		if (all >= MOD) all -= MOD;
	}
	std::cout << all << std::endl;
	
	return 0;
}