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>
template <typename T>
T Max(const T &x, const T &y) {
  return x < y ? y : x;
}
template <typename T>
T Min(const T &x, const T &y) {
  return x < y ? x : y;
}
template <typename T>
int chkmax(T &x, const T &y) {
  return x < y ? (x = y, 1) : 0;
}
template <typename T>
int chkmin(T &x, const T &y) {
  return x > y ? (x = y, 1) : 0;
}
template <typename T>
void read(T &x) {
  T f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  x *= f;
}
const int maxn = 1000010, mod = 1000000007, inv = 500000004;
int n, m, num[maxn], mx, L, bit[maxn];
int a[maxn], A[18][maxn], B[18][maxn], tmp[maxn];
int C[maxn], D[maxn], E[maxn], fib[maxn], ans;
void FWT_OR(int *, int, int);
void FWT_XOR(int *, int, int);
void FWT_AND(int *, int, int);
void Mul(int *, int *, int, int *);
int main() {
  read(m);
  for (int i = (1), iend = (m); i <= iend; ++i)
    read(num[i]), chkmax(mx, num[i]);
  for (n = 1; n <= mx; n <<= 1) L++;
  fib[1] = 1;
  for (int i = (2), iend = (n - 1); i <= iend; ++i)
    fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  for (int i = (1), iend = (n - 1); i <= iend; ++i)
    for (int j = (0), jend = (L - 1); j <= jend; ++j)
      if ((i >> j) & 1) bit[i]++;
  for (int i = (1), iend = (m); i <= iend; ++i) a[num[i]]++;
  Mul(a, a, L, C);
  FWT_XOR(a, L, 1);
  for (int i = (0), iend = (n - 1); i <= iend; ++i)
    E[i] = 1LL * a[i] * a[i] % mod;
  FWT_XOR(a, L, -1);
  FWT_XOR(E, L, -1);
  for (int i = (0), iend = (n - 1); i <= iend; ++i) {
    C[i] = 1LL * C[i] * fib[i] % mod;
    D[i] = 1LL * a[i] * fib[i] % mod;
    E[i] = 1LL * E[i] * fib[i] % mod;
  }
  FWT_AND(C, L, 1);
  FWT_AND(D, L, 1);
  FWT_AND(E, L, 1);
  for (int i = (0), iend = (n - 1); i <= iend; ++i)
    C[i] = 1LL * C[i] * D[i] % mod * E[i] % mod;
  FWT_AND(C, L, -1);
  for (int i = 1; i < n; i <<= 1) ans = (ans + C[i]) % mod;
  printf("%d\n", ans);
  return 0;
}
void Mul(int *a, int *b, int L, int *c) {
  int n = 1 << L;
  for (int i = (0), iend = (n - 1); i <= iend; ++i) {
    c[i] = 0;
    for (int sub = i;; sub = (sub - 1) & i) {
      c[i] = (c[i] + 1LL * a[sub] * b[i ^ sub]) % mod;
      if (!sub) break;
    }
  }
}
void FWT_OR(int *a, int L, int type) {
  int n = 1 << L;
  for (int j = (0), jend = (L - 1); j <= jend; ++j)
    for (int i = (0), iend = (n - 1); i <= iend; ++i)
      if ((i >> j) & 1)
        a[i] = (1LL * a[i] + type * a[i ^ (1 << j)] + mod) % mod;
}
void FWT_AND(int *a, int L, int type) {
  int n = 1 << L;
  for (int j = (0), jend = (L - 1); j <= jend; ++j)
    for (int i = (n - 1), iend = (0); i >= iend; --i)
      if (!((i >> j) & 1))
        a[i] = (1LL * a[i] + type * a[i | (1 << j)] + mod) % mod;
}
void FWT_XOR(int *a, int L, int type) {
  int n = 1 << L;
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += (i << 1))
      for (int k = (0), kend = (i - 1); k <= kend; ++k) {
        int x = a[j + k], y = a[j + k + i];
        a[j + k] = (x + y) % mod;
        a[j + k + i] = (1LL * x - y + mod) % mod;
        if (type == -1) {
          a[j + k] = 1LL * a[j + k] * inv % mod;
          a[j + k + i] = 1LL * a[j + k + i] * inv % mod;
        }
      }
}