Problem: Zero AND Subsets

Given a multiset of nonnegative integers a_1, a_2, .., a_N.

How many non-empty subsets of this set have a value bitwiseAND of 0?

Find the remainder of the answer divided by 10 ^ 9 + 7.

input


N
a_1 a_2 ... a_N


output

Divide the answer by 10 ^ 9 + 7 and output the remainder.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 0 \ leq a_i \ leq 2 ^ {20} -1



Input example


6
8 6 9 1 2 1


Output example


51






Example

Input

6
8 6 9 1 2 1


Output

51

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

template <unsigned Mod> struct ModularInt {
  using M = ModularInt;
  unsigned v;
  ModularInt(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {}
  M operator-() const { return M() -= *this; }
  M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; }
  M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; }
  friend M operator*(M l, M r) { return l *= r; }
  friend M operator/(M l, M r) { return l /= r; }
  friend M operator+(M l, M r) { return l += r; }
  friend M operator-(M l, M r) { return l -= r; }
  M pow(long long n) const {
    assert(n >= 0);
    M res = 1;
    for (M t = *this; n; t *= t, n >>= 1) if (n & 1) res *= t;
    return res;
  }
  M inv() const { assert(v != 0); return pow(Mod - 2); }
  friend string to_string(M a) { return to_string(a.v); }
};
constexpr unsigned mod = 1e9 + 7;
using Mint = ModularInt<mod>;

template<class T> void fzt(vector<T>& a) {
  int n = a.size();
  assert(__builtin_popcount(n) == 1);
  for (int i = 0; 1 << i < n; ++i) {
    for (int S = 0; S < n; ++S) if (~S & 1 << i) {
      a[S] += a[S | 1 << i];
    }
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vector<int> a(1 << 20);
  int n;
  cin >> n;
  while (n--) {
    int x;
    cin >> x;
    ++a[x];
  }
  fzt(a);
  Mint res;
  for (int s = 0; s < 1 << 20; ++s) {
    if (__builtin_parity(s)) {
      res -= Mint(2).pow(a[s]);
    } else {
      res += Mint(2).pow(a[s]);
    }
  }
  cout << res.v << '\n';
}