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

public class a
{
	public static void main(String[] arg) throws IOException
	{
		new a();
	}
	final long MOD = 1_000_000_007;
	final int stop = 1_000_001;
	long pow(long base, long exp)
	{
		if(exp == 0) return 1;
		if((exp&1) != 0) return base*pow(base, exp-1)%MOD;
		long ret = pow(base, exp/2);
		return ret*ret%MOD;
	}
	public a() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		int n = in.nextInt();
		int[] dp = new int[stop];
		for(int i = 0; i < n; i++) dp[in.nextInt()]++;
		for(int i = 0; i < 20; i++)
		{
			for(int bm = 0; bm < stop; bm++)
			{
				if(((1<<i)&bm) != 0)
				{
					dp[bm^(1<<i)] += dp[bm];
				}
			}
		}
		long ans = 0;
		long[] two = new long[stop];
		two[0] = 1;
		for(int i = 1; i < two.length; i++)
		{
			two[i] = two[i-1]*2%MOD;
		}
		for(int bm = 0; bm < stop; bm++)
		{
			if(Integer.bitCount(bm)%2 == 0)
			{
				ans += two[(int)dp[bm]];
				ans %= MOD;
			}
			else
			{
				ans -= two[(int)dp[bm]];
				ans += MOD;
				ans %= MOD;
			}
		}
		ans++;
		ans %= MOD;
		System.out.println(ans);
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException
		{
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}