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>
using namespace std;
#pragma warning (disable: 4996)

long long mod = 1000000007;
long long N, A[1 << 20], power[1 << 20];
long long dp[1 << 20];

int main() {
	scanf("%lld", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &A[i]);
		dp[A[i]]++;
	}
	for (int i = 0; i < 20; i++) {
		for (int j = 0; j < (1 << 20); j++) {
			if ((j & (1 << i)) != 0) dp[j - (1 << i)] += dp[j];
		}
	}
	power[0] = 1; for (int i = 1; i < (1 << 20); i++) power[i] = (2LL * power[i - 1]) % mod;

	long long sum = 0;
	for (int i = 0; i < (1 << 20); i++) {
		int cnt = 0;
		for (int j = 0; j < 20; j++) { if ((i / (1 << j)) % 2 == 1) cnt++; }
		if (cnt % 2 == 0) sum += power[dp[i]];
		else sum -= power[dp[i]];
	}
	sum += mod * mod; sum %= mod;
	cout << sum << endl;
	return 0;
}