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
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int dp[1 << 20] = {};
const ll MOD = 1e9+7;
ll fac[MAX_N];

int main() {
    int n;
    cin >> n;

    

    int a[n];
    rep(i,n){
        cin >> a[i];
        dp[a[i]]++;
    }

    rep(i,20) rep(b, 1 << 20) if(0 == (b & (1 << i))) dp[b] += dp[b | (1 << i)];

    rep(i,MAX_N){
        if(i == 0){
            fac[i] = 1;
        }else{
            fac[i] = fac[i-1] * 2 % MOD;
        }
    }

    ll ans = 0;

    rep(i,1 << 20){
        if(__builtin_popcount(i) % 2 == 1){
            ans += MOD - (fac[dp[i]] - 1);
        }else{
            ans += fac[dp[i]] - 1;
        }
        ans %= MOD;
    }

    cout << ans << endl;
    return 0;
}
 
 

