abcdabcdab
5
2 2 8 ab
2 1 10 ab
1 3 a
1 4 b
2 1 4 ab

1
3
2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  template <typename Arg1>
  void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
  }
  template <typename Arg1, typename... Args>
  void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  }
#else
#define trace(...)
#endif
const int L = 17 ;
const int L2 = 1<<L ;
const int mod = 1e9+7 ;
int sbits[L2] ;
vi oddbits ;
inline int add(int x,int y)
{
  x+=y;
  if(x>=mod) x-=mod;
  if(x<0) x+=mod;
  return x;
}
inline int mult(int x,int y)
{
  ll tmp=(ll)x*y;
  if(tmp>=mod) tmp%=mod;
  return tmp;
}
inline int pwmod(int x,int y)
{
  int ans=1;
  while(y){if(y&1)ans=mult(ans,x);y>>=1;x=mult(x,x);}
  return ans;
}
vector<ii> nus[L] ;
void zeta(int A[L2])
{
  FN(i,L)
  {
    for(ii m:nus[i]) A[m.fi]=add(A[m.fi],A[m.se]) ;
  }
}

void meu(int A[L2])
{
    for(int i:oddbits) A[i] = mod - A[i] ;
    zeta(A) ;
  for(int i:oddbits) A[i] = mod - A[i] ;
}
void conv(int A[L2],int B[L2])
{
     zeta(A), zeta(B);//return
     FN(i,L2) A[i]=mult(A[i],B[i]);
     meu(A);
}
int t[L+1][L2],t1[L2] ;
void subsetconv(int A[L2],int ans[L2])
{
  FN(i,L2) t[sbits[i]][i] = A[i] ;
  FN(i,L+1) zeta(t[i]) ;
  FN(c,L+1) FN(a,c+1)
    {
    int *t2 = t[a], *t3 = t[c-a] ;
    FN(i,L2) t1[i]=mult(t2[i],t3[i]) ;
    meu(t1) ;
        FN(i,L2) if(sbits[i] == c) ans[i]=add(ans[i],t1[i]) ;
    }
}
vector<ii> su[L] ;

void transform(int p[L2],bool inv=false){ int u,v;
for(int len=1,l=2;l<=L2;len<<=1,l<<=1)for(int
i=0;i<L2;i+=l) FN(j,len){
u=p[i+j],v=p[i+j+len] ;
if(inv) {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}
else {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}}
if(inv){int d=pwmod(L2,mod-2);FN(i,L2)p[i]=mult(p[i],d);} }

int cnt[L2],fib[L2],A[L2],B[L2],C[L2],a[L2],b[L2],c[L2] ;

int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  FN(i,L2)
  {
    sbits[i] = __builtin_popcount(i) ;
    if(sbits[i] & 1) oddbits.emplace_back(i) ;
    FN(j,L)
    {
      if(i&(1<<j)) nus[j].emplace_back(mp(i,i^(1<<j))) ;
      if((i&(1<<j)) == 0) su[j].emplace_back(mp(i,i^(1<<j))) ;
    }
  }
  FN(i,L) reverse(all(su[i])) ;
  fib[1] = 1 ; rep(i,2,L2) fib[i] = add(fib[i-1],fib[i-2]) ;

  int N,x ; cin>>N ;
  FN(i,N)
  {
    cin>>x, ++cnt[x] ;
  }

  subsetconv(cnt,A) ;
  FN(i,L2) A[i]=mult(A[i],fib[i]) ;

  FN(i,L2) B[i]=mult(cnt[i],fib[i]);
  FN(i,L2) C[i]=cnt[i] ;
  transform(C) ;
  FN(i,L2) C[i]=mult(C[i],C[i]) ;
  transform(C,1) ;
  FN(i,L2) C[i]=mult(C[i],fib[i]) ;
  int ans = 0 ;
  FN(p,L)
  {
    FN(i,L2) a[i]=b[i]=c[i]=0 ;
    for(ii m:nus[p]) a[m.se]=A[m.fi],b[m.se]=B[m.fi],c[m.se]=C[m.fi] ;
    FN(i,L)
    {
      for(ii m:su[i])
      {
        a[m.fi]=add(a[m.fi],a[m.se]) ;
        b[m.fi]=add(b[m.fi],b[m.se]) ;
        c[m.fi]=add(c[m.fi],c[m.se]) ;
      }
    }
    FN(i,L2) a[i]=mult(a[i],mult(b[i],c[i])) ;
    meu(a) ;
    ans = add(ans,a[(1<<L)-1]) ;
  }
  ans = ans == 0 ? 0 : mod - ans ;
  cout << ans << "\n" ;
  return 0 ;
}