#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

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

#define ull unsigned long long

using namespace std;

const int N = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int cnt[<<], bin[N], num[<<], n;

int main() {

    for(int i = bin[] = ; i < N; i++) bin[i] = bin[i - ] *  % mod;

    scanf("%d", &n);

    for(int i = ; i <= n; i++) {

        int x; scanf("%d", &x);

        cnt[x]++;

    }

    for(int i = ; i < ; i++)

        for(int S = ; S < ( << ); S++)

            if(S >> i & ) cnt[S ^ ( << i)] += cnt[S];

    LL ans = bin[n];

    for(int S = ; S < ( << ); S++) {

        num[S] = num[S-(S&-S)] + ;

        if(num[S] & ) ans = (ans - bin[cnt[S]] + mod) % mod;

        else ans = (ans + bin[cnt[S]]) % mod;

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/