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


public class D {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;

    int MAX_BITS = 20;
    int MAX = (1 << MAX_BITS);
    int N;
    long[] cnt;

	public void solve() throws IOException {				
		N = nextInt();
        cnt = new long[MAX];
		for (int i = 0; i < N; i++) {
            cnt[nextInt()]++;
        }

        for (int bit = MAX_BITS-1; bit >= 0; bit--) {
            for (int mask = MAX-1; mask >= 0; mask--) {
                if ( (mask & (1 << bit)) != 0) {
                    cnt[mask ^ (1 << bit)] = mod_add(cnt[mask ^ (1 << bit)], cnt[mask]);
                }
            }
        }

        long ans = 0;
        for (int mask = 0; mask < MAX; mask++) {
            if (cnt[mask] == 0) continue;
//            out.println(mask + ": " + cnt[mask]);
            if (Integer.bitCount(mask) % 2 == 0) {
                ans = mod_add(ans, mod_min(mod_power(2, cnt[mask]), 1));
            } else {
                ans = mod_min(ans, mod_min(mod_power(2, cnt[mask]), 1));
            }
        }
        out.println(ans);
	}

    long MOD = (int) 1e9 + 7;
    public long mod_add(long n1, long n2){
        return (n1 + n2) % MOD;
    }
    public long mod_min(long n1, long n2){
        return (n1 + MOD - n2) % MOD;
    }
    public long mod_time(long n1, long n2){
        return (n1 * n2) % MOD;
    }
    public long mod_power(long a, long k) {
        if (k == 0) return 1;
        if (k % 2 == 0) return mod_power(a * a % MOD, k / 2);
        return a * mod_power(a, k - 1) % MOD;
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new D().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}