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>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll inf = 3e18;
const char sp = ' ';

int N, a[100000];
ll cnt[1 << 20], DP[1 << 20];

ll pw(ll x, int y) {
	ll a = 1;
	while (y) {
		if (y & 1)a = a * x%mod;
		x = x * x%mod;
		y /= 2;
	}
	return a;
}



int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for (int j = 0; j < 20; j++) {
		for (int i = (1 << 20) - 1; i >= 0; i--) {
			if (!(i&(1 << j))) {
				cnt[i] += cnt[i | (1 << j)];
			}
		}
	}
	ll res = 0;
	for (int i = 0; i < (1 << 20); i++) {
		int c = 0;
		for (int j = 0; j < 20; j++) {
			c += ((i >> j) & 1);
		}
		if (c & 1) {
			res -= pw(2, cnt[i]);
		}
		else {
			res += pw(2, cnt[i]);
		}
		res = (res + mod) % mod;
	}
	cout << res << endl;
}