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>
inline int read() {
  int out(0), c(getchar());
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c <= '9' && c >= '0'; c = getchar())
    out = (out << 3) + (out << 1) + (c ^ 48);
  return out;
}
const int MAXN = 1 << 17 | 100;
const int pm = 1e9 + 7, inv2 = 5e8 + 4;
int N, L;
int f[MAXN], cnt[MAXN];
int F[MAXN], G[MAXN];
int A[MAXN], B[MAXN];
inline void Add(int &a, const int &b) {
  a += b;
  a -= (a >= pm) * pm;
  a += (a < 0) * pm;
}
inline int cou(int s) {
  int out = 0;
  for (; s; out += s & 1, s >>= 1)
    ;
  return out;
}
void fwt_or(int a[], const int tg) {
  for (int n = 2; n <= N; n <<= 1)
    for (int l = 0, m = n >> 1; l < N; l += n)
      for (int i = 0; i < m; ++i) Add(a[l + i + m], tg * a[l + i]);
}
void fwt_and(int a[], const int tg) {
  for (int n = 2; n <= N; n <<= 1)
    for (int l = 0, m = n >> 1; l < N; l += n)
      for (int i = 0; i < m; ++i) Add(a[l + i], tg * a[l + i + m]);
}
void fwt_xor(int a[], const int tg) {
  for (int n = 2, x, y; n <= N; n <<= 1) {
    for (int l = 0, m = n >> 1; l < N; l += n) {
      for (int i = 0; i < m; ++i) {
        x = a[l + i], y = a[l + i + m];
        a[l + i] = (long long)(x + y) * tg % pm;
        a[l + i + m] = (long long)(x - y + pm) * tg % pm;
      }
    }
  }
}
void mul_or(int c[], int a[], int b[]) {
  for (int i = 0; i < N; ++i) A[i] = a[i], B[i] = b[i];
  fwt_or(A, 1), fwt_or(B, 1);
  for (int i = 0; i < N; ++i) c[i] = (long long)A[i] * B[i] % pm;
  fwt_or(c, -1);
}
void mul_and(int c[], int a[], int b[]) {
  for (int i = 0; i < N; ++i) A[i] = a[i], B[i] = b[i];
  fwt_and(A, 1), fwt_and(B, 1);
  for (int i = 0; i < N; ++i) c[i] = (long long)A[i] * B[i] % pm;
  fwt_and(c, -1);
}
void mul_xor(int c[], int a[], int b[]) {
  for (int i = 0; i < N; ++i) A[i] = a[i], B[i] = b[i];
  fwt_xor(A, 1), fwt_xor(B, 1);
  for (int i = 0; i < N; ++i) c[i] = (long long)A[i] * B[i] % pm;
  fwt_xor(c, inv2);
}
void mul_sub(int c[], int a[], int b[]) {
  static int A[18][MAXN], B[18][MAXN], C[18][MAXN], tmp[MAXN];
  for (int i = 0; i < N; ++i) {
    A[cou(i)][i] = a[i];
    B[cou(i)][i] = b[i];
  }
  for (int i = 1; i <= 17; ++i) {
    for (int j = 0; j <= i; ++j) {
      mul_or(tmp, A[j], B[i - j]);
      for (int x = 0; x < N; ++x) Add(C[i][x], tmp[x]);
    }
  }
  for (int i = 0; i < N; ++i) c[i] = C[cou(i)][i];
}
int main() {
  L = read(), N = 1 << 17;
  for (int i = 1; i <= L; ++i) ++cnt[read()];
  f[0] = 0, f[1] = 1;
  for (int i = 2; i < N; ++i) f[i] = (f[i - 1] + f[i - 2]) % pm;
  mul_sub(F, cnt, cnt);
  for (int i = 0; i < N; ++i) F[i] = (long long)F[i] * f[i] % pm;
  mul_xor(G, cnt, cnt);
  for (int i = 0; i < N; ++i) G[i] = (long long)G[i] * f[i] % pm;
  for (int i = 0; i < N; ++i) f[i] = (long long)f[i] * cnt[i] % pm;
  mul_and(F, F, f);
  mul_and(F, F, G);
  int ans = 0;
  for (int i = 0; i <= 16; ++i) Add(ans, F[1 << i]);
  printf("%d\n", ans);
  return 0;
}