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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int N;
int A[2000000];
int F[2000000][25];
int cnt[2000000];
long long Ans = 0;
long long MOD = 1000000007;
long long two(int x) {
  if (x == 0) return 1;
  long long p = two(x / 2);
  if (x % 2)
    return p * p * 2 % MOD;
  else
    return p * p % MOD;
}
int main() {
  cin >> N;
  for (int Ni = 0; Ni < N; Ni++) {
    cin >> A[Ni];
    F[A[Ni]][0]++;
  }
  int n = (1 << 20);
  for (int bi = 1, di = 1; bi <= 20; bi++, di *= 2)
    for (int i = 0; i <= n; i++) {
      if (i & di)
        F[i][bi] = F[i][bi - 1], cnt[i]++;
      else
        F[i][bi] = F[i][bi - 1] + F[i + di][bi - 1];
    }
  for (int i = 0; i <= n; i++) {
    int f = cnt[i] % 2 ? -1 : 1;
    long long p = two(F[i][20]);
    Ans += f * (p - 1);
    Ans %= MOD;
    Ans += MOD;
    Ans %= MOD;
  }
  cout << Ans << endl;
}