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;
long mod=1e9+7;
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
int N;
int cnt[1<<20];
int main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		int a;cin>>a;cnt[a]++;
	}
	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];
	long ans=0;
	for(int i=0;i<1<<20;i++)
	{
		long now=power(2,cnt[i]);
		ans+=__builtin_popcount(i)%2?-now:now;
	}
	cout<<(ans%mod+mod)%mod<<endl;
}