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 int lim = (1 << 17);
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x * f;
}
int cnt[233333], n, A[18][233333], B[18][233333], C[233333], D[233333],
    E[233333], f[233333], ans;
inline int bits(int x) { return __builtin_popcount(x); }
void FMT(int *f, int x) {
  for (int i = 0; i < 17; ++i)
    for (int j = 0; j < lim; ++j)
      if (j >> i & 1)
        f[j] = (f[j] + (x ? f[j ^ (1 << i)] : mod - f[j ^ (1 << i)])) % mod;
}
void FWT_and(int *f, int x, int n) {
  for (int p = 2; p <= n; p <<= 1) {
    int len = p >> 1;
    for (int k = 0; k < n; k += p) {
      for (int i = k; i < k + len; ++i) {
        f[i] = (f[i] + (x ? f[i + len] : mod - f[i + len])) % mod;
      }
    }
  }
}
void FWT_xor(int *f, int x, int n) {
  for (int p = 2; p <= n; p <<= 1) {
    int len = p >> 1;
    for (int k = 0; k < n; k += p) {
      for (int i = k; i < k + len; ++i) {
        int l = (x ? f[i] : 1LL * f[i] * inv2 % mod);
        int r = (x ? f[i + len] : 1LL * f[i + len] * inv2 % mod);
        f[i] = (l + r) % mod, f[i + len] = (l - r + mod) % mod;
      }
    }
  }
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    ++cnt[read()];
  }
  f[1] = 1;
  for (int i = 2; i <= lim; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
  }
  for (int i = 0; i < lim; ++i) {
    A[bits(i)][i] = cnt[i];
    C[i] = D[i] = cnt[i];
  }
  for (int i = 0; i <= 17; ++i) {
    FMT(A[i], 1);
  }
  for (int s = 0; s < lim; ++s) {
    for (int i = 0; i <= 17; ++i) {
      for (int j = 0; j <= i; ++j) {
        B[i][s] = (B[i][s] + 1LL * A[j][s] * A[i - j][s]) % mod;
      }
    }
  }
  for (int i = 0; i <= 17; ++i) {
    FMT(B[i], 0);
  }
  FWT_xor(C, 1, lim);
  for (int i = 0; i < lim; ++i) {
    C[i] = 1LL * C[i] * C[i] % mod;
  }
  FWT_xor(C, 0, lim);
  for (int i = 0; i < lim; ++i) {
    C[i] = 1LL * C[i] * f[i] % mod, D[i] = 1LL * D[i] * f[i] % mod;
    E[i] = 1LL * B[bits(i)][i] * f[i] % mod;
  }
  FWT_and(C, 1, lim), FWT_and(D, 1, lim), FWT_and(E, 1, lim);
  for (int i = 0; i < lim; ++i) {
    E[i] = 1LL * C[i] * D[i] % mod * E[i] % mod;
  }
  FWT_and(E, 0, lim);
  for (int i = 0; i < 17; ++i) {
    ans = (ans + E[1 << i]) % mod;
  }
  printf("%d\n", ans);
  return 0;
}