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;
int cnt[1 << 17];
const long long MOD = 1e9 + 7, INV2 = (MOD + 1) >> 1;
long long add(long long x, long long y) {
  return x + y >= MOD ? x + y - MOD : x + y;
}
long long sub(long long x, long long y) { return x >= y ? x - y : x + MOD - y; }
void FWT(long long *a, int n, int op) {
  for (int d = 2; d <= (1 << n); d <<= 1) {
    int m = d >> 1;
    for (int i = 0; i < (1 << n); i += d) {
      for (int j = 0; j < m; j++) {
        int x = a[i + j], y = a[i + j + m];
        if (op == 0)
          a[i + j + m] = add(x, y);
        else if (op == 1)
          a[i + j] = add(x, y);
        else
          a[i + j] = add(x, y), a[i + j + m] = sub(x, y);
      }
    }
  }
}
void UFWT(long long *a, int n, int op) {
  for (int d = 2; d <= (1 << n); d <<= 1) {
    int m = d >> 1;
    for (int i = 0; i < (1 << n); i += d) {
      for (int j = 0; j < m; j++) {
        int x = a[i + j], y = a[i + j + m];
        if (op == 0)
          a[i + j + m] = sub(y, x);
        else if (op == 1)
          a[i + j] = sub(x, y);
        else
          a[i + j] = add(x, y) * INV2 % MOD,
                a[i + j + m] = sub(x, y) * INV2 % MOD;
      }
    }
  }
}
int cntbit[1 << 17];
long long A[18][1 << 17], B[18][1 << 17], C[18][1 << 17];
void PROD(long long *a, long long *b, long long *c, int n, int op) {
  if (op >= -1 && op <= 1) {
    FWT(a, n, op);
    FWT(b, n, op);
    for (int i = 0; i < (1 << n); i++) c[i] = a[i] * b[i] % MOD;
    UFWT(c, n, op);
    return;
  }
  for (int i = 1; i < (1 << n); i++) cntbit[i] = cntbit[i >> 1] + (i & 1);
  memset(A, 0, sizeof(A)), memset(B, 0, sizeof(B));
  for (int i = 0; i < (1 << n); i++)
    A[cntbit[i]][i] = a[i], B[cntbit[i]][i] = b[i];
  for (int i = 0; i <= n; i++) FWT(A[i], n, 0), FWT(B[i], n, 0);
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < (1 << n); k++)
        C[i][k] = add(C[i][k], A[j][k] * B[i - j][k] % MOD);
    }
    UFWT(C[i], n, 0);
    for (int k = 0; k < (1 << n); k++)
      if (cntbit[k] == i) c[k] = add(c[k], C[i][k]);
  }
}
long long a[1 << 17], b[1 << 17], c[1 << 17], d[1 << 17], e[1 << 17];
long long u[1 << 17], v[1 << 17];
const int N = 17;
long long fib[1 << 17];
int main() {
  int n = 0;
  scanf("%d", &n);
  for (int i = 1, s = 0; i <= n; i++) scanf("%d", &s), cnt[s]++;
  for (int i = 0; i < (1 << N); i++) a[i] = b[i] = c[i] = d[i] = e[i] = cnt[i];
  PROD(a, b, u, N, 2), PROD(d, e, v, N, -1);
  fib[0] = 0, fib[1] = 1;
  for (int i = 2; i < (1 << N); i++) fib[i] = add(fib[i - 1], fib[i - 2]);
  for (int i = 0; i < (1 << N); i++)
    u[i] = u[i] * fib[i] % MOD, v[i] = v[i] * fib[i] % MOD,
    c[i] = c[i] * fib[i] % MOD;
  PROD(u, c, a, N, 1);
  PROD(v, a, u, N, 1);
  long long ans = 0;
  for (int i = 0; i < N; i++) ans = add(ans, u[1 << i]);
  printf("%lld", ans);
  return 0;
}