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 <iostream>
#include <set>
#include <utility>
#include <vector>
#include <algorithm>
#define llint long long
#define inf 1e18
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[100005];
llint cnt[1<<20];
llint pop[1<<20];

void zeta_transform(llint a[], int n)
{
	int S = 1<<n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < S; j++){
			if(!(j&(1<<i))) a[j] += a[j^(1<<i)], a[j] %= mod;
		}
	}
}

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
	zeta_transform(cnt, 20);
	for(int i = 0; i < (1<<20); i++) cnt[i] = modpow(2, cnt[i]) + mod - 1, cnt[i] %= mod;
	for(int i = 1; i < (1<<20); i++) pop[i] = pop[i&(i-1)] + 1;
	
	llint ans = 0;
	for(int i = 0; i < (1<<20); i++){
		if(pop[i]%2) ans += mod - cnt[i], ans %= mod;
		else ans += cnt[i], ans %= mod;
	}
	cout << ans << endl;

	return 0;
}