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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int B = 17;
const int N = 1 << B;
const long long int M = (int)1e9 + 7;
const long long int inv2 = (int)5e8 + 4;
namespace Mobius {
int count[N];
void init_count() {
  for (int i = 0; i < N; ++i) count[i] = __builtin_popcount(i);
}
void mobius_transform(long long int A[], long long int inv = 1ll) {
  for (int i = 0; i < B; ++i)
    for (int j = 0; j < N; ++j)
      if (j >> i & 1) {
        A[j] += inv * A[j ^ 1 << i] % M;
        A[j] += M;
        if (A[j] >= M) A[j] -= M;
      }
}
void ranked_mobius(long long int A[], long long int ans[][N]) {
  for (int k = 0; k <= B; ++k) {
    long long int* a = ans[k];
    for (int i = 0; i < N; ++i)
      if (count[i] == k)
        a[i] = A[i];
      else
        a[i] = 0;
    mobius_transform(a);
  }
}
void inverse_ranked_mobius(long long int A[][N], long long int ans[]) {
  for (int k = 0; k <= B; ++k) {
    long long int* a = A[k];
    mobius_transform(a, -1);
    for (int i = 0; i < N; ++i)
      if (count[i] == k) ans[i] = a[i];
  }
}
long long int frm[B + 1][N];
long long int grm[B + 1][N];
long long int fg[B + 1][N];
void subset_convolution(long long int f[], long long int g[],
                        long long int ans[]) {
  memset(frm, 0, sizeof frm);
  memset(grm, 0, sizeof grm);
  memset(fg, 0, sizeof fg);
  ranked_mobius(f, frm);
  ranked_mobius(g, grm);
  for (int k = 0; k <= B; ++k)
    for (int X = 0; X < N; ++X)
      for (int r = 0; r <= k; ++r) {
        fg[k][X] += frm[r][X] * grm[k - r][X] % M;
        if (fg[k][X] >= M) fg[k][X] -= M;
      }
  inverse_ranked_mobius(fg, ans);
}
};  // namespace Mobius
using namespace Mobius;
long long int cnt[N], fib[N], ab[N], Xor[N], And[N];
void transform_xor(long long int x[], bool inv = 0) {
  for (int mid = 1, i = 2; i <= N; mid = i, i <<= 1)
    for (int j = 0, lo = 0; lo < N; j + 1 == mid ? (lo += i, j = 0) : ++j) {
      long long int tw1 = x[lo + j], tw2 = x[lo + j + mid];
      if (inv) {
        x[lo + j] = (tw1 + tw2) % M * inv2 % M;
        x[lo + j + mid] = (tw1 - tw2 + M) % M * inv2 % M;
      } else {
        x[lo + j] = tw1 + tw2;
        if (x[lo + j] >= M) x[lo + j] -= M;
        x[lo + j + mid] = tw1 - tw2;
        if (x[lo + j + mid] < 0) x[lo + j + mid] += M;
      }
    }
}
void transform_and(long long int p[], bool inv = 0) {
  for (int len = 1; (len << 1) <= N; len <<= 1)
    for (int i = 0; i < N; i += (len << 1))
      for (int j = 0; j < len; ++j) {
        long long int tw1 = p[i + j];
        long long int tw2 = p[i + len + j];
        if (!inv) {
          p[i + j] = tw2;
          p[i + len + j] = tw1 + tw2;
          if (p[i + len + j] >= M) p[i + len + j] -= M;
        } else {
          p[i + j] = tw2 - tw1;
          if (p[i + j] < 0) p[i + j] += M;
          p[i + len + j] = tw1;
        }
      }
}
void solve(std::istream& in, std::ostream& out) {
  fib[0] = 0, fib[1] = 1;
  for (int i = 2; i < N; ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= M) fib[i] -= M;
  }
  int n;
  in >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    in >> x;
    ++cnt[x];
  }
  init_count();
  subset_convolution(cnt, cnt, ab);
  memcpy(Xor, cnt, sizeof cnt);
  transform_xor(Xor);
  for (int i = 0; i < N; ++i) Xor[i] = Xor[i] * Xor[i] % M;
  transform_xor(Xor, 1);
  for (int i = 0; i < N; ++i)
    Xor[i] = Xor[i] * fib[i] % M, ab[i] = ab[i] * fib[i] % M,
    cnt[i] = cnt[i] * fib[i] % M;
  transform_and(Xor);
  transform_and(ab);
  transform_and(cnt);
  for (int i = 0; i < N; ++i) And[i] = Xor[i] * ab[i] % M * cnt[i] % M;
  transform_and(And, 1);
  long long int ans = 0;
  for (int i = 1; i < N; i <<= 1) ans = (ans + And[i]) % M;
  out << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve(cin, cout);
  return 0;
}