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.IOException;
import java.io.InputStreamReader;

public class D {

    private static final long MOD = 1000000007;
    
    public long solve(int n, int[] a) {
        long[] dp = new long[1<<20];
        for (int i=0; i<n; i++)
            dp[a[i]]++;
        for (int k=1; k<=20; k++)
            for (int i=0; i<1<<20; i++)
                if (((i>>(20-k))&1)==1)
                    dp[i] = dp[i];
                else
                    dp[i] = (dp[i] + dp[i|(1<<(20-k))])%MOD;
        long res = 0;
        for (int i=0; i<1<<20; i++) {
            int bitNum = Long.bitCount(i);
            if (bitNum%2==0)
                res = (res+pow2(dp[i]))%MOD;
            else
                res = (res-pow2(dp[i])+MOD)%MOD;
        }
        return res;
    }
    
    private long pow2(long n) {
        long res = 1;
        long x = 2;
        while (n>0) {
            if ((n&1)==1)
                res = (res*x)%MOD;
            x = (x*x)%MOD;
            n>>=1;
        }
        return res;
    }
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = null;
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            String line = br.readLine();
            int n = Integer.parseInt(line);
            line = br.readLine();
            String[] split = line.split(" ");
            int[] a = new int[n];
            for (int i=0; i<n; i++)
                a[i] = Integer.parseInt(split[i]);
            long res = new D().solve(n, a);
            System.out.println(res);
        } finally {
            if (br!=null)
                br.close();
        }
    }
}