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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 100005
#define MAX 20

int N;
ll dp[1 << MAX];
ll POW[SIZE];


int main(){

	POW[0] = 1;
	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
		POW[i] %= MOD;
	}

	scanf("%d",&N);

	for(int i = 0; i < POW[MAX]; i++){

		dp[i] = 0;
	}

	int tmp;
	for(int loop = 0; loop < N; loop++){

		scanf("%d",&tmp);
		dp[tmp] += 1;
	}

	for(int loop = 0; loop < MAX; loop++){
		for(int state = POW[MAX]-1; state >= 0; state--){
			if((state & (1 << loop)) == 0){
				//自分を含む集合の個数を求める
				dp[state] += dp[state+POW[loop]];
			}
		}
	}

	ll ans = POW[N]-1;
	ll minus = 0;

	//全体から、少なくとも1つ以上の桁が1である集合を除く
	for(int i = 1; i < POW[MAX]; i++){
		int count = 0;
		for(int loop = 0; loop < MAX; loop++){
			if(i & (1 << loop))count++;
		}

		if(count%2 == 1){

			minus += (POW[dp[i]]-1);
			minus %= MOD;
		}else{

			minus -= (POW[dp[i]]-1);
			if(minus < 0){
				minus += MOD;
			}
		}
	}

	ans -= minus;
	if(ans < 0){

		ans += MOD;
	}

	printf("%lld\n",ans);

	return 0;
}