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 static java.lang.Math.*; 
import java.io.*; 
import java.util.*; 

public class A {
	BufferedReader in; 
	PrintWriter out;
	StringTokenizer st; 


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

	public int nextInt() {
		return Integer.parseInt(next()); 
	}
	public long nextLong() {
		return Long.parseLong(next());
	}

	boolean bit(int m, int i) {
		return (m & (1 << i)) > 0; 
	}

	int n, x, y, c, m, k;  

	long mod = 1000000007L;


	public void run() {
		in  = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		n = nextInt();
		long[] g = new long[1<<20];

		for (int i=0; i<n; i++) {
			g[nextInt()]++;
		}

		long[] f = new long[n+2]; 
		f[1] = 1; 
		for (int i=2; i<=n; i++) f[i] = ((f[i-1] * 2L + 1) % mod);


		for (int i=0; i<20; i++) {
			for (int m=0; m<(1<<20); m++) if (bit(m, i)) g[m ^ (1 << i)]+=g[m];
		}


		long tot=0;
		for (int m=1; m<(1<<20); m++) {
			int cnt = 0;
			for (int i=0; i<20; i++) if (bit(m, i)) cnt++;

			if (cnt % 2 == 0) {
				tot = (tot - f[(int)g[m]] + mod) % mod; 
			} else {
				tot = (tot + f[(int)g[m]]) % mod; 
			}
			//System.err.println(tot);
		}
		
		tot = (f[n] - tot + mod) % mod; 
		out.println(tot);

		out.close(); 
	}

	class Pair implements Comparable<Pair> {
		int x;
		long y; 
		public Pair(int x, long y) {
			this.x=x; 
			this.y=y; 
		}
		public int compareTo(Pair o) {
			if (y != o.y) return sign(y - o.y); 
			return x - o.x; 
		}
	}

	int sign(long x) {
		if (x < 0) return -1; 
		if (x > 0) return 1; 
		return 0;
	}

	public static void main(String[] args) throws Exception {
		new A().run(); 		
	}
}