题解
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i, s, t) for(int i = s, __ = t; i <= __; ++i)
#define dwn(i, s, t) for(int i = s, __ = t; i >= __; --i)
const int INF = 2147483647;
const int MAXN = 100 + (1 << 19);
const int MOD = 1000000007;
using namespace std;
inline int read(int x = 0, int f = 1){
char ch = getchar();
for(; !isdigit(ch); ch = getchar())if(ch == '-')f = -1;
for(; isdigit(ch); ch = getchar())x = ch - '0' + x * 10;
return x * f;
}
inline void write(int x){
if(x < 0)putchar('-'), x = -x;
if(x >= 10)write(x / 10); putchar(x % 10 + '0');
return ;
}
inline int add(int x, int y){x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y){x -= y; return x < 0 ? x + MOD : x;}
inline void inc(int &x, int y){x += y, x -= x >= MOD ? MOD : 0; return ;}
inline void dec(int &x, int y){x -= y, x += x < 0 ? MOD : 0; return ;}
inline int mul(int x, int y){return (ll)x * y % MOD;}
inline int fpow(int x, int y, int tmp = 1){
while(y){if(y & 1)tmp = mul(tmp, x); x = mul(x, x), y >>= 1;} return tmp;
}
inline int inv(int x){return fpow(x, MOD -2);}
inline int die(int x, int y){return (ll)x * inv(y) % MOD;}
int n, lim = 1, a[MAXN], ans, inv2;
void fwt_or(int *u, int tag){
for(int i = 1; i < lim; i <<= 1)
for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1)
inc(u[j + k + i], ~tag ? u[j + k] : sub(0, u[j + k]));
return ;
}
void fwt_and(int *u, int tag){
for(int i = 1; i < lim; i <<= 1)
for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1)
inc(u[j + k], ~tag ? u[j + k + i] : sub(0, u[j + k + i]));
return ;
}
void fwt_xor(int *u,int tag){
for(int i = 1;i < lim; i <<= 1)
for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1){
int x = u[j + k], y = u[j + k + i];
u[j + k] = add(x, y), u[j + k + i] = sub(x, y);
if(tag == -1){
u[j + k] = mul(u[j + k], inv2);
u[j + k + i] = mul(u[j + k + i], inv2);
}
}
return ;
}
int bc[MAXN], s[19][MAXN], X[19][MAXN], o[MAXN];
void solve_or(){
rep(i, 0, bc[lim])fwt_or(s[i], 1);
rep(now, 0, lim)X[0][now] = mul(s[0][now], s[0][now]);
rep(i, 1, bc[lim]){
rep(j, 0, i)rep(now, 0, lim)
inc(X[i][now], mul(s[j][now], s[i - j][now]));
fwt_or(X[i], -1);
rep(now, 0, lim)if(bc[now] != i)X[i][now] = 0;
if(i != bc[lim])fwt_or(X[i], 1);
}
rep(i, 0, bc[lim] - 1)fwt_or(X[i], -1);
rep(now, 0, lim)o[now] = mul(X[bc[now]][now], a[now]);
return ;
}
int p[MAXN], q[MAXN];
void solve_xor(){
inv2 = inv(2); fwt_xor(p, 1);
rep(now, 0, lim)p[now] = mul(p[now], p[now]); fwt_xor(p, -1);
rep(now, 0, lim)p[now] = mul(p[now], a[now]); return ;
}
void solve_final(){
rep(now, 0, lim)q[now] = mul(q[now], a[now]);
fwt_and(o, 1); fwt_and(p, 1); fwt_and(q, 1);
rep(now, 0, lim)q[now] = mul(o[now], mul(p[now], q[now]));
fwt_and(q, -1);
for(int i = 1; i < lim; i <<= 1)inc(ans, q[i]);
return ;
}
int main(){
n = read(); int tmp = 0;
rep(now, 0, 1 << 18)bc[now] = bc[now >> 1] + (now & 1);
rep(i, 1, n){
int x = read(); tmp = max(tmp, x);
s[bc[x]][x]++, p[x]++, q[x]++;
}
while(lim - 1 <= tmp)lim <<= 1; lim--;
a[0] = 0, a[1] = 1; rep(i, 2, lim)a[i] = add(a[i - 1], a[i - 2]);
solve_or(); solve_xor(); solve_final();
write(ans); return 0;
}