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>
const long long mod = 1000000007;
const long long inv2 = (mod + 1) / 2;
const long long P = 17;
const long long N = 1 << P;
long long f[N];
void FWT_And(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  FWT_And(A, len2);
  FWT_And(A + len2, len2);
  for (long long i = 0; i < len2; ++i) A[i] = (A[i] + A[i + len2]) % mod;
}
void IFWT_And(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  for (long long i = 0; i < len2; ++i) A[i] = (A[i] - A[i + len2]) % mod;
  IFWT_And(A, len2);
  IFWT_And(A + len2, len2);
}
void FWT_Or(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  FWT_Or(A, len2);
  FWT_Or(A + len2, len2);
  for (long long i = 0; i < len2; ++i) A[i + len2] = (A[i + len2] + A[i]) % mod;
}
void IFWT_Or(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  for (long long i = 0; i < len2; ++i) A[i + len2] = (A[i + len2] - A[i]) % mod;
  IFWT_Or(A, len2);
  IFWT_Or(A + len2, len2);
}
void FWT_Xor(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  FWT_Xor(A, len2);
  FWT_Xor(A + len2, len2);
  for (long long i = 0; i < len2; ++i) {
    long long x = A[i], y = A[i + len2];
    A[i] = (x + y) % mod;
    A[i + len2] = (x - y) % mod;
  }
}
void IFWT_Xor(long long *A, long long len) {
  if (len == 1) return;
  long long len2 = len >> 1;
  for (long long i = 0; i < len2; ++i) {
    long long x = A[i], y = A[i + len2];
    A[i] = (x + y) * inv2 % mod;
    A[i + len2] = (x - y) * inv2 % mod;
  }
  IFWT_Xor(A, len2);
  IFWT_Xor(A + len2, len2);
}
long long tmp[N], A[N], B[N], C[N];
int main() {
  f[0] = 0;
  f[1] = 1;
  for (long long i = 2; i < N; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  long long n;
  std::cin >> n;
  long long x;
  while (n--) {
    std::cin >> x;
    ++A[x];
    ++C[x];
  }
  for (long long a = 0; a < N; ++a) {
    long long t = (N - 1) & ~a;
    for (long long b = t;; b = (b - 1) & t) {
      B[a | b] = (B[a | b] + A[a] * A[b]) % mod;
      if (!b) break;
    }
  }
  FWT_Xor(A, N);
  for (long long i = 0; i < N; ++i) A[i] = A[i] * A[i] % mod;
  IFWT_Xor(A, N);
  for (long long i = 0; i < N; ++i) A[i] = f[i] * A[i] % mod;
  for (long long i = 0; i < N; ++i) B[i] = f[i] * B[i] % mod;
  for (long long i = 0; i < N; ++i) C[i] = f[i] * C[i] % mod;
  FWT_And(A, N);
  FWT_And(B, N);
  FWT_And(C, N);
  for (long long i = 0; i < N; ++i) A[i] = A[i] * B[i] % mod * C[i] % mod;
  IFWT_And(A, N);
  long long ans = 0;
  for (long long i = 0; i < P; ++i) ans = (ans + A[1 << i]) % mod;
  printf("%I64d\n", (ans + mod) % mod);
  return 0;
}