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;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int cnt(int n) {
  int res = 0;
  while(n > 0) {
    res += n % 2;
    n /= 2;
  }
  return res;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  vi v(1<<20);
  for(int i=0;i<n;++i) {
    int a; cin >> a;
    v[a]++;
  }

  for(int i=0;i<20;++i) {
    for(int j=0;j<(1<<20);++j) {
      if((j>>i)&1) {
        v[j-(1<<i)] += v[j];
      }
    }
  }

  vll po(n);
  po[0] = 1;
  for(int i=0;i<n;++i) {
    po[i+1] = po[i] * 2 % MOD;
  }

  ll ans = 0;
  for(int i=0;i<(1<<20);++i) {
    if(cnt(i) % 2 == 0) {
      ans += po[v[i]];
      ans %= MOD;
    } else {
      ans += MOD - po[v[i]];
      ans %= MOD;
    }
  }
  cout << ans << endl;

}