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 m = (1 << 17), mo = 1e9 + 7;
int n, A[((1 << 17) + 1)], F[((1 << 17) + 1)], f[((1 << 17) + 1)][20],
    a[((1 << 17) + 1)], b[((1 << 17) + 1)], c[((1 << 17) + 1)],
    bt[((1 << 17) + 1)], z[20], I, ans;
void inc(int &x, int y) { x = x + y >= mo ? x + y - mo : x + y; }
void dec(int &x, int y) { x = x - y < 0 ? x - y + mo : x - y; }
long long fpm(long long x, long long y) {
  long long s = 1;
  while (y) {
    if (y & 1) s = (s * x) % mo;
    y >>= 1, x = (x * x) % mo;
  }
  return s;
}
int main() {
  int i, j, k, x, y;
  scanf("%d", &n);
  F[1] = 1;
  for (i = 2; i < m; i++) F[i] = (F[i - 1] + F[i - 2]) % mo;
  while (n--) scanf("%d", &x), A[x]++;
  for (i = 1; i < m; i++) bt[i] = bt[i - (i & (-i))] + 1;
  for (i = 0; i < m; i++) f[i][bt[i]] = A[i];
  for (i = 0; i < 17; i++)
    for (j = 0; j < m; j++)
      if ((j >> i) & 1)
        for (k = 0; k < 18; k++) inc(f[j][k], f[j ^ (1 << i)][k]);
  for (i = 0; i < m; i++) {
    memset(z, 0, sizeof(z));
    for (j = 0; j < 18; j++)
      for (k = 0; j + k < 18; k++)
        z[j + k] = (z[j + k] + 1LL * f[i][j] * f[i][k]) % mo;
    for (j = 0; j < 18; j++) f[i][j] = z[j];
  }
  for (i = 0; i < 17; i++)
    for (j = 0; j < m; j++)
      if ((j >> i) & 1)
        for (k = 0; k < 18; k++) dec(f[j][k], f[j ^ (1 << i)][k]);
  for (i = 0; i < m; i++)
    a[i] = 1LL * F[i] * f[i][bt[i]] % mo, b[i] = 1LL * A[i] * F[i] % mo;
  for (i = 2; i <= m; i <<= 1)
    for (j = 0; j < m; j += i)
      for (k = 0; k < i / 2; k++) {
        x = A[j + k], y = A[j + k + i / 2];
        A[j + k] = x + y >= mo ? x + y - mo : x + y;
        A[j + k + i / 2] = x - y < 0 ? x - y + mo : x - y;
      }
  for (i = 0; i < m; i++) A[i] = 1LL * A[i] * A[i] % mo;
  for (i = 2; i <= m; i <<= 1)
    for (j = 0; j < m; j += i)
      for (k = 0; k < i / 2; k++) {
        x = A[j + k], y = A[j + k + i / 2];
        A[j + k] = x + y >= mo ? x + y - mo : x + y;
        A[j + k + i / 2] = x - y < 0 ? x - y + mo : x - y;
      }
  I = fpm(m, mo - 2);
  for (i = 0; i < m; i++) A[i] = 1LL * A[i] * I % mo;
  for (i = 0; i < m; i++) c[i] = 1LL * A[i] * F[i] % mo;
  for (i = 0; i < 17; i++)
    for (j = 0; j < m; j++)
      if ((j >> i) & 1) {
        inc(a[j ^ (1 << i)], a[j]);
        inc(b[j ^ (1 << i)], b[j]);
        inc(c[j ^ (1 << i)], c[j]);
      }
  for (i = 0; i < m; i++) a[i] = 1LL * a[i] * b[i] % mo * c[i] % mo;
  for (i = 0; i < 17; i++)
    for (j = 0; j < m; j++)
      if ((j >> i) & 1) dec(a[j ^ (1 << i)], a[j]);
  for (i = 0; i < 17; i++) inc(ans, a[1 << i]);
  cout << ans;
  return 0;
}