<h2>题目大意</h2>

有 $n$ 个元素，求有多少个子集满足它们的按位或的答案是 $0$。
$n,a_i \leq 10^6$

<h2>题解</h2>

其实这篇是来水的因为题目比较简单
答案是 $0$ 也就是每一位都是 $0$，发现 $log_2(10^6) \approx 19.9315685693 \leq 20$ ，所以我们可以对于每一位分别容斥。我们现在容斥枚举一个 $S$ 需要求出 $S$ 的位置一定填 $1$，其他位置无限制的方案数。我们将每个数也看成一个状压的01 集合的话，设 $f_{s}$ 表示集合 $s$ 出现的次数，也就是求

$$\sum_{s1 \supseteq S} f_{s1}$$

也就是 $S$ 的超集和，这个可以用高维前缀和轻松解决。
时间复杂度 $O(nlogn)$$

/*
 * Author: RainAir
 * Time: 2019-08-28 09:35:37
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1e7 + 5;
const int ha = 1e9 + 7;

int f[MAXN],pc[MAXN],pw2[MAXN];
int n;

inline int qpow(int a,int n){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

inline void FMT(){
    FOR(i,0,20){
        FOR(S,0,(1<<20)-1){
            if(!(S&(1<<i))) f[S] += f[S|(1<<i)];
        }
    }
}

signed main(){
    scanf("%lld",&n);
    FOR(i,1,MAXN-1) pc[i] = pc[i>>1]+(i&1);pw2[0] = 1;
    FOR(i,1,n){
        int x;scanf("%lld",&x);
        f[x]++;
    }
    FMT();int ans = 0;
    FOR(S,0,(1<<20)-1){
        ans = (ans+qpow(2,f[S])*(pc[S]&1?-1:1)+ha)%ha;
    }
    printf("%lldn",ans);
    return 0;
}