Problem: You are given an array s of n non-negative integers.

A 5-tuple of integers (a, b, c, d, e) is said to be valid if it satisfies the following conditions: 

  * 1 ≤ a, b, c, d, e ≤ n
  * (sa | sb) & sc & (sd ^ se) = 2i for some integer i
  * sa & sb = 0



Here, '|' is the bitwise OR, '&' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of f(sa|sb) * f(sc) * f(sd^se) over all valid 5-tuples (a, b, c, d, e), where f(i) is the i-th Fibonnaci number (f(0) = 0, f(1) = 1, f(i) = f(i - 1) + f(i - 2)).

Since answer can be is huge output it modulo 109 + 7.

Input

The first line of input contains an integer n (1 ≤ n ≤ 106).

The second line of input contains n integers si (0 ≤ si < 217).

Output

Output the sum as described above, modulo 109 + 7

Examples

Input

2
1 2


Output

32


Input

3
7 4 1


Output

3520


Input

10
1 3 0 7 3 7 6 5 7 5


Output

1235424


Input

10
50 9 11 44 39 40 5 39 23 7


Output

113860062

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2, class T3 = hash<T1>>
using umap = unordered_map<T1, T2, T3>;
template <class T>
using uset = unordered_set<T>;
template <class T>
using vec = vector<T>;
const long long infll = numeric_limits<long long>::max() >> 1;
const long long inf = numeric_limits<long long>::max() >> 1;
const long long mod = 1e9 + 7;
const long long N = 1e6 + 1;
const long long M = 1 << 17;
const long long K = 17;
long long n, ans;
long long s[N];
long long f[N];
vec<long long> cnt;
void input() {
  cin >> n;
  cnt.resize(M);
  for (long long i = 1; i <= n; ++i) {
    cin >> s[i];
    cnt[s[i]]++;
  }
}
void calc_fib() {
  f[0] = 0;
  f[1] = 1;
  for (long long i = 2; i < N; ++i) {
    f[i] = f[i - 1] + f[i - 2];
    f[i] %= mod;
  }
}
long long fpow(long long b, long long p = mod - 2) {
  long long res = 1;
  long long pow = b;
  for (; p; p >>= 1) {
    if (p & 1) {
      res *= pow;
      res %= mod;
    }
    pow *= pow;
    pow %= mod;
  }
  return res;
}
void transform(vec<long long> &a, bool invert, long long w, long long x,
               long long y, long long z) {
  long long n = (long long)a.size();
  for (long long cur = 2; cur <= n; cur <<= 1) {
    for (long long i = 0; i < n; i += cur) {
      for (long long j = 0; j < cur / 2; ++j) {
        long long ix = i + j;
        long long iy = i + j + cur / 2;
        long long u = a[ix];
        long long v = a[iy];
        a[ix] = w * u + x * v;
        a[iy] = y * u + z * v;
        a[ix] %= mod;
        a[ix] += mod;
        a[iy] += mod;
        a[iy] %= mod;
      }
    }
  }
  if (invert && abs(w * z - y * x) == 2) {
    for (long long &e : a) {
      e *= fpow(n, mod - 2);
      e %= mod;
    }
  }
}
vec<long long> hadamard(vec<long long> &a, vec<long long> &b, long long w1,
                        long long x1, long long y1, long long z1, long long w2,
                        long long x2, long long y2, long long z2) {
  vec<long long> fa = a;
  vec<long long> fb = b;
  long long n = 1;
  while (n < (long long)fa.size() + (long long)fb.size()) n <<= 1;
  fa.resize(n);
  fb.resize(n);
  transform(fa, false, w1, x1, y1, z1);
  transform(fb, false, w1, x1, y1, z1);
  for (long long i = 0; i < n; ++i) {
    fa[i] *= fb[i];
    fa[i] %= mod;
  }
  transform(fa, true, w2, x2, y2, z2);
  return fa;
}
vec<long long> subset(vec<long long> &cnt) {
  vec<long long> res(M);
  for (long long i = 0; i < M; ++i) {
    long long inv = M - i - 1;
    for (long long mask = inv;; mask = (mask - 1) & inv) {
      res[i | mask] += cnt[i] * cnt[mask];
      res[i | mask] %= mod;
      if (!mask) {
        break;
      }
    }
  }
  return res;
}
void solve() {
  calc_fib();
  vec<long long> c1 = subset(cnt);
  vec<long long> c3 = hadamard(cnt, cnt, 1, 1, 1, -1, 1, 1, 1, -1);
  vec<long long> c2 = cnt;
  for (long long i = 0; i < M; ++i) {
    assert(c3[i] >= 0);
    c1[i] *= f[i];
    c2[i] *= f[i];
    c3[i] *= f[i];
    c1[i] %= mod;
    c2[i] %= mod;
    c3[i] %= mod;
  }
  vec<long long> res = c1;
  res = hadamard(res, c2, 1, 1, 0, 1, 1, -1, 0, 1);
  res = hadamard(res, c3, 1, 1, 0, 1, 1, -1, 0, 1);
  for (long long i = 1; i < M; ++i) {
    if (!(i & (i - 1))) {
      ans += res[i];
      ans %= mod;
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  input();
  solve();
}