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.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author George Marcus
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    private static final int K = 20;
    private static final int MOD = 1000000007;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int N = in.nextInt();
        int[][] dp = new int[2][1 << K];
        for (int i = 0; i < N; i++) {
            dp[0][in.nextInt()]++;
        }

        int line = 1;
        for (int k = 1; k <= K; k++) {
            for (int x = 0; x < (1 << K); x++) {
                dp[line][x] = dp[1 - line][x];
                if ((x & (1 << (k - 1))) == 0) {
                    dp[line][x] += dp[1 - line][x | (1 << (k - 1))];
                    if (dp[line][x] >= MOD) {
                        dp[line][x] -= MOD;
                    }
                }
            }
            line = 1 - line;
        }
        line = 1 - line;

        int[] p2 = new int[N + 1];
        p2[0] = 1;
        for (int i = 1; i <= N; i++) {
            p2[i] = p2[i - 1] + p2[i - 1];
            if (p2[i] >= MOD) {
                p2[i] -= MOD;
            }
        }

        int[] size = new int[1 << K];
        int ans = 0;
        for (int x = 0; x < (1 << K); x++) {
            if (x > 0) {
                size[x] = size[x & (x - 1)] + 1;
            }

            int num = dp[line][x];
            int crt = p2[num] - 1;
            if ((size[x] & 1) > 0) {
                ans -= crt;
                if (ans < 0) {
                    ans += MOD;
                }
            }
            else {
                ans += crt;
                if (ans >= MOD) {
                    ans -= MOD;
                }
            }
        }

        out.println(ans);
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));

        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}