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;
const long long mod = 1e9 + 7, inv2 = (mod + 1) / 2;
const int lim = (1 << 17);
int bit[lim + 2];
long long sav[lim + 2], fib[lim + 2];
const long long Cor[2][2] = {{1, 0}, {1, 1}},
                ICor[2][2] = {{1, 0}, {mod - 1, 1}};
const long long Cand[2][2] = {{0, 1}, {1, 1}},
                ICand[2][2] = {{mod - 1, 1}, {1, 0}};
const long long Cxor[2][2] = {{1, mod - 1}, {1, 1}},
                ICxor[2][2] = {{inv2, inv2}, {mod - inv2, inv2}};
inline void FWT(long long *A, const long long c[2][2]) {
  for (int l = 1; l < lim; l <<= 1)
    for (int i = 0; i < lim; i += (l << 1))
      for (int j = i; j < i + l; j++) {
        long long tmp = A[j];
        A[j] = (c[0][0] * A[j] % mod + c[0][1] * A[j + l] % mod) % mod;
        A[j + l] = (c[1][0] * tmp % mod + c[1][1] * A[j + l] % mod) % mod;
      }
}
inline void bitmul(long long *A, long long *B, long long *res,
                   const long long c[2][2], const long long ic[2][2]) {
  for (int i = 0; i < lim; i++) sav[i] = A[i], res[i] = B[i];
  FWT(sav, c), FWT(res, c);
  for (int i = 0; i < lim; i++) res[i] = res[i] * sav[i] % mod;
  FWT(res, ic);
}
long long tmp1[18][lim + 2], tmp2[18][lim + 2];
inline void submul(long long *A, long long *res) {
  memset(tmp2, 0, sizeof(tmp2));
  for (int i = 0; i < lim; i++) tmp1[bit[i]][i] = A[i];
  for (int i = 0; i <= 17; i++) FWT(tmp1[i], Cor);
  for (int i = 0; i <= 17; i++) {
    for (int j = 0; j <= i; j++)
      for (int s = 0; s < lim; s++)
        tmp2[i][s] = (tmp2[i][s] + tmp1[j][s] * tmp1[i - j][s] % mod) % mod;
    FWT(tmp2[i], ICor);
  }
  for (int i = 0; i < lim; i++) res[i] = tmp2[bit[i]][i];
}
long long f[lim + 2], g[lim + 2], h[lim + 2], ans[lim + 2];
int main() {
  fib[1] = 1;
  for (int i = 2; i < lim; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  bit[0] = 0;
  for (int i = 1; i < lim; i++) bit[i] = bit[i ^ (i & (-i))] + 1;
  int n, v;
  long long sum = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &v);
    f[v]++, g[v]++, h[v]++;
  }
  submul(f, f), bitmul(h, h, h, Cxor, ICxor);
  for (int i = 0; i < lim; i++) {
    f[i] = f[i] * fib[i] % mod;
    g[i] = g[i] * fib[i] % mod;
    h[i] = h[i] * fib[i] % mod;
  }
  bitmul(f, g, ans, Cand, ICand);
  bitmul(ans, h, ans, Cand, ICand);
  for (int i = 0; i < 17; i++) sum = (sum + ans[1 << i]) % mod;
  printf("%lld\n", sum);
  return 0;
}