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;
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
ll modpow(ll x, ll p, ll mod) {
  x %= mod, (p %= mod - 1) < 0 ? p += mod - 1 : 0LL;
  ll res = 1LL;
  while (p > 0) {
    if (p & 1) res = res * x % mod;
    (x *= x) %= mod, p >>= 1;
  }
  return res;
}
template <int mod>
struct Mint {
  int x;
  Mint(ll x = 0) : x(int((x %= mod) < 0 ? x + mod : x)) {}
  Mint& operator+=(const Mint& rhs) {
    if ((x += rhs.x) >= mod) x -= mod;
    return *this;
  }
  Mint& operator-=(const Mint& rhs) { return *this += mod - rhs.x; }
  Mint& operator*=(const Mint& rhs) {
    x = int((1LL * x * rhs.x) % mod);
    return *this;
  }
  Mint& operator/=(const Mint& rhs) {
    return *this *= Mint(modpow(rhs.x, mod - 2, mod));
  }
  Mint operator+(const Mint& rhs) const { return Mint(*this) += rhs; }
  Mint operator-(const Mint& rhs) const { return Mint(*this) -= rhs; }
  Mint operator*(const Mint& rhs) const { return Mint(*this) *= rhs; }
  Mint operator/(const Mint& rhs) const { return Mint(*this) /= rhs; }
  Mint power(ll p) const { return Mint(modpow(x, p, mod)); }
  bool operator==(const Mint& rhs) const { return x == rhs.x; }
  bool operator<(const Mint& rhs) const { return x < rhs.x; }
  friend ostream& operator<<(ostream& out, const Mint& a) { return out << a.x; }
  friend istream& operator>>(istream& in, Mint& a) {
    ll x;
    in >> x;
    a = Mint(x);
    return in;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  constexpr int mod = 1e9 + 7, N = 20, fullmask = (1 << N) - 1;
  using Mi = Mint<mod>;
  vector<Mi> F(1 << N, 1);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    F[fullmask ^ a] *= Mi(2);
  }
  for (int i = 0; i < N; ++i)
    for (int mask = 0; mask < (1 << N); ++mask)
      if (mask >> i & 1) F[mask] *= F[mask ^ (1 << i)];
  vector<int> sgn(1 << N);
  sgn[0] = (N % 2 ? -1 : +1);
  Mi ans = F[0] * sgn[0];
  for (int mask = 1; mask < (1 << N); ++mask) {
    sgn[mask] = -sgn[mask & (mask - 1)];
    ans += F[mask] * sgn[mask];
  }
  cout << ans << '\n';
  exit(0);
}