Discription

Jzzhu have n non-negative integers a₁, a₂, ..., a_n. We will call a sequence of indexes i₁, i₂, ..., i_k(1 ≤ i₁ < i₂ < ... < i_k ≤ n) a group of size k.

Jzzhu wonders, how many groups exists such that a_i1 & a_i2 & ... & a_ik = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (10⁹ + 7). Operation x & y denotes bitwise AND operation of two numbers.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁶). The second line contains n integers a₁, a₂, ..., a_n(0 ≤ a_i ≤ 10⁶).

Output

Output a single integer representing the number of required groups modulo 1000000007 (10⁹ + 7).

Examples

Input

3 2 3 3

Output

0

Input

4 0 1 2 3

Output

10

Input

6 5 2 0 5 2 1

Output

53     很明显的套路题。     我们可以用类似FMT的方法让所有a[]的子集的cnt++，然后统计出对于每种集合 i 的f[i]，即选出一堆数and的集合包含i的方案数。     显然f[i] = 2^cnt[i] - 1。     然后直接容斥就行了2333

#include
        
         #define ll long longusing namespace std;const int maxn=1000005,ha=1e9+7;inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}inline int read(){	int x=0; char ch=getchar();	for(;!isdigit(ch);ch=getchar());	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';	return x;}int ci[maxn],n,f[maxn],ans,b[maxn];inline void solve(){	for(int i=0;i<=20;i++)	    for(int j=1;j<=1e6;j++) if(ci[i]&j) f[j^ci[i]]+=f[j];		for(int i=0;i<=1e6;i++) ADD(ans,b[i]?add(ci[f[i]],ha-1):add(ha-ci[f[i]],1));}int main(){	n=read();		ci[0]=1; for(int i=1;i<=1e6;i++) ci[i]=add(ci[i-1],ci[i-1]);	b[0]=1; for(int i=1;i<=1e6;i++) b[i]=b[i^(i&-i)]^1;		for(int i=1;i<=n;i++) f[read()]++;		solve();		printf("%d\n",ans);	return 0;}