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;

typedef long long ll;
typedef pair<int,int> P;
ll const mod = 1e9+7;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

ll pow_mod(ll a,ll b) {
    ll ret;
    if (b < 0) ret = pow_mod(a,mod+b-1);
    else if (b == 0) ret = 1;
    else if (b == 1) ret = a;
    else {
        ll c = pow_mod(a,b/2);
        if (b%2) ret = (c*c)%mod*a%mod;
        else ret = c*c%mod;
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    vector<ll> dp1(1<<20,0),dp2(1<<20,0);
    for (int i = 0;i < n;++i) {
        int a;
        cin >> a;
        dp1[a]++;
    }
    for (int i = 0;i < 20;++i) for (int j = 0;j < (1<<20);++j) if (!(j&(1<<i))) (dp1[j] += dp1[j|(1<<i)]) %= mod;
    for (int i = 0;i < (1<<20);++i) dp2[i] = pow_mod(2,dp1[i])-1;
    for (int i = 0;i < 20;++i) for (int j = 0;j < (1<<20);++j) if (!(j&(1<<i))) (dp2[j] -= dp2[j|(1<<i)]) %= mod;
    cout << (dp2[0]+mod)%mod << endl;
    // p_ary(dp1,0,1<<4);
    // p_ary(dp2,0,1<<4);
}