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 = (long long int)1e9 + 7;
const long long int invN = (long long int)742744451;
namespace Mobius {
int count[N];
void init_count() {
  for (int i = 0; i < N; ++i) count[i] = __builtin_popcount(i);
}
void mobius_transform(int A[], 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];
        if (1ll * A[j] >= M)
          A[j] = 1ll * A[j] - M;
        else if (A[j] < 0)
          A[j] = 1ll * A[j] + M;
      }
}
void ranked_mobius(int A[], int ans[][N]) {
  for (int k = 0; k <= B; ++k) {
    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(int A[][N], int ans[]) {
  for (int k = 0; k <= B; ++k) {
    int* a = A[k];
    mobius_transform(a, -1);
    for (int i = 0; i < N; ++i)
      if (count[i] == k) ans[i] = a[i];
  }
}
int frm[B + 1][N];
int grm[B + 1][N];
int fg[B + 1][N];
void subset_convolution(int f[], int g[], int ans[]) {
  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] += 1ll * frm[r][X] * grm[k - r][X] % M;
        if (1ll * fg[k][X] >= M) fg[k][X] -= M;
      }
  inverse_ranked_mobius(fg, ans);
}
void transform_and(int A[], int inv = 1) {
  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];
        if (1ll * A[j] >= M)
          A[j] = 1ll * A[j] - M;
        else if (A[j] < 0)
          A[j] = 1ll * A[j] + M;
      }
}
void and_convolution(int f[], int g[], int h[], int ans[]) {
  transform_and(f);
  transform_and(g);
  transform_and(h);
  for (int i = 0; i < N; ++i) ans[i] = 1ll * f[i] * g[i] % M * h[i] % M;
  transform_and(ans, -1);
}
};  // namespace Mobius
using namespace Mobius;
int cnt[N], fib[N], ab[N], Xor[N], And[N];
void transform_xor(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) {
      int tw1 = x[lo + j], tw2 = x[lo + j + mid];
      x[lo + j] = tw1 + tw2;
      if (1ll * x[lo + j] >= M) x[lo + j] = 1ll * x[lo + j] - M;
      x[lo + j + mid] = tw1 - tw2;
      if (x[lo + j + mid] < 0) x[lo + j + mid] = 1ll * x[lo + j + mid] + M;
    }
  if (inv)
    for (int i = 0; i < N; ++i) {
      x[i] = (1ll * x[i] * invN) % M;
    }
}
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 (1ll * fib[i] >= M) fib[i] = 1ll * 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] = 1ll * Xor[i] * Xor[i] % M;
  transform_xor(Xor, 1);
  for (int i = 0; i < N; ++i)
    Xor[i] = 1ll * Xor[i] * fib[i] % M, ab[i] = 1ll * ab[i] * fib[i] % M,
    cnt[i] = 1ll * cnt[i] * fib[i] % M;
  and_convolution(Xor, ab, cnt, And);
  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;
}