Problem: Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k. 

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

Input

The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

Output

Output a single integer representing the number of required groups modulo 1000000007 (109 + 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

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


import java.util.StringTokenizer;

public class JzzhuAndNumbersTut {
	void log(Object o){

		//System.out.println(o);
			 output(o);

	}

	void info(Object o){
		System.out.println(o);
		//output(o);
	}

	void output(Object o){

		outputWln(""+o+"\n");

	}

	void outputWln(Object o){
		//		 System.out.print(o);

		try {
			out.write(""+ o);
		} catch (Exception e) {

		}
	}


	String next(){
		while (st== null|| !st.hasMoreTokens()) {
			try {
				st=new StringTokenizer(in.readLine());
			} catch (Exception e) {
			}
		}
		return st.nextToken();
	}

	String nextLine(){
		try {
			return in.readLine();
		} catch (Exception e) {
		}
		return null;
	}

	int nextInt(){
		return Integer.parseInt(next());
	}


	long nextLong(){
		return Long.parseLong(next());


	}

	int ln2(int x){
		int u=1;
		int k=0;
		while (2*u<=x){
			u=u*2;
			k++;
		}
		return k;
	}
	
	long powerMod(long b,long e,long m){
    	long x=1;
    	while (e>0) {
    		if (e%2==1)
    			x=(b*x)%m;
    		b=(b*b)%m;
    		e=e/2;
    	}
    	return x; 
    }
	
	
	int[][] F;

	void solve(){
		int MAX=1;
		int L=1;
		L=21;
		MAX= 1 << (L-1);
		
		/*
		while (MAX<max) {
			MAX*=2;
			L++;
		}
		
		*/
	//	log("L:"+L+" MAX:"+MAX);
		F=new int[MAX][L];
		for (int i=0;i<N;i++)
			F[A[i]][0]++;
		int mask=1;
		for (int k=1;k<L;k++){
			for (int x=0;x<MAX;x++){
				if ((x & mask)==mask)
					F[x][k]=F[x][k-1];
				else
					F[x][k]=F[x][k-1]+F[(x | mask)][k-1];
			}
			mask*=2;
		}
		//for (int x=0;x<MAX;x++)
		//	log("x:"+x+" F[x]:"+F[x][L-1]);
		long count=0;
		for (int x=0;x<MAX;x++){
			long a=powerMod(2,(long)(F[x][L-1]),MOD);
			int g=Integer.bitCount(x);
			if (g%2==0)
				count+=a;
			else
				count-=a;
			if (count<0){
				count%=MOD;
				count+=MOD;
			}
			if (count>=MOD)
				count%=MOD;
		}
		output(count);
	}
	

	// Global vars
	StringTokenizer st;
	BufferedReader in;
	BufferedWriter out;
	int N;
	int[] A;
	int MOD=1000000007;
	int max;
	
	
	

	
	void process() throws Exception {


		out = new BufferedWriter(new OutputStreamWriter(System.out));
		in=new BufferedReader(new InputStreamReader(System.in));

		N=nextInt();
		A=new int[N];
		max=0;
		for (int i=0;i<N;i++){
			A[i]=nextInt();
			if (A[i]>max)
				max=A[i];
		}
		solve();
		
		
		try {
			out.close();
		}
		catch (Exception e){}


	}



	public static void main(String[] args) throws Exception {
		JzzhuAndNumbersTut J=new JzzhuAndNumbersTut();


		J.process();


	}


}

/*

 not my solution
//algo taken from editorial: http://codeforces.com/blog/entry/13112


/* explication de l'algo 


On prend M la plus petite puissance de 2 supérieure strictement à tous les A[i]
Et L l'exposant

on cherche toutes les k-chaines dont le résultat est zero
cela veut dire que pour tout x, k-chaine & x =0

il suffit de tester les x tel que x a un seul bit mis 

on pose C(i) = ensemble des chaînes compatibles avec le bit "i" mis


E = ensemble des chaînes. Cardinal = pow(2,N)

on cherche cardinal de E- union(C(i))

on applique principe inclusion / exclusion

res = card[E] + (-1)k (intersection de k ensemble C(i))

or une k-chaîne appartient à l'intersection de k  (Ci) revient ) à dire que k chaîne & x == x pour x défini par les bits en question

mais en fait si un k-chaine est compatible avec x, alors c'est vrai pour tous les éléments A qui composent la k-chaine

donc on pose, pour x<M, on note H(x)={i tel que x ^ A[i] = x}
Et F(x)=# H(x) (cardinal)
Le cardinal de l'intersection des (Ci) est pow(2,F(x)) pour le x correspondant aux Ci


Il faut maintenant calculer F(x)
cela se fait par récurrence sur L, par la méthode proposée dans le  tutorial


*/