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 MOD = 1e9 + 7, N = 1e6 + 10, FN = (1 << 17), TOP = 17, inv2 = 5e8 + 4;
int s[N], fib[FN + 10], cnt1[N], f[TOP + 1][FN + 10], g[TOP + 1][FN + 10];
int cntor[FN + 10], val_s[FN + 10], val_or[FN + 10], val_xor[FN + 10],
    ans[FN + 10];
int n, m, Ans;
void prework(int n);
void fwt(int *a, int op, int type, int len);
void fst();
void get_FibVal(int *a, int *b);
int main() {
  int x;
  prework(FN);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &x), ++s[x];
  fst();
  get_FibVal(val_or, cntor);
  get_FibVal(val_s, s);
  fwt(s, 1, 2, FN);
  for (int i = 0; i < FN; ++i) s[i] = 1LL * s[i] * s[i] % MOD;
  fwt(s, -1, 2, FN);
  get_FibVal(val_xor, s);
  fwt(val_s, 1, 1, FN);
  fwt(val_or, 1, 1, FN);
  fwt(val_xor, 1, 1, FN);
  for (int i = 0; i < FN; ++i)
    ans[i] = 1LL * val_s[i] * val_or[i] % MOD * val_xor[i] % MOD;
  fwt(ans, -1, 1, FN);
  for (int i = 1; i < FN; i <<= 1) Ans = (Ans + ans[i]) % MOD;
  printf("%d\n", Ans);
}
void prework(int n) {
  fib[0] = 0;
  fib[1] = 1;
  for (int i = 2; i <= n; ++i) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
void fwt(int *a, int op, int type, int len) {
  int v, u;
  for (int step = 2; step <= len; step <<= 1)
    for (int st = 0; st < len; st += step)
      for (int i = 0; i < step >> 1; ++i) {
        u = a[st + i];
        v = a[st + i + (step >> 1)];
        if (op == 1) {
          if (type == 2)
            a[st + i] = (u + v) % MOD,
                   a[st + i + (step >> 1)] = (u + MOD - v) % MOD;
          else if (type == 1)
            a[st + i] = (u + v) % MOD;
          else
            a[st + i + (step >> 1)] = (u + v) % MOD;
        } else {
          if (type == 2)
            a[st + i] = 1LL * (u + v) * inv2 % MOD,
                   a[st + i + (step >> 1)] =
                       1LL * (1LL * u + MOD - v) * inv2 % MOD;
          else if (type == 1)
            a[st + i] = (1LL * u - v + MOD) % MOD;
          else
            a[st + i + (step >> 1)] = (1LL * v - u + MOD) % MOD;
        }
      }
}
void fst() {
  for (int i = 0; i < FN; ++i)
    for (int j = 0; j <= TOP; ++j) cnt1[i] += i >> j & 1;
  for (int i = 0; i < FN; ++i) f[cnt1[i]][i] += s[i];
  for (int i = 0; i <= TOP; ++i) fwt(f[i], 1, 0, FN);
  for (int i = 0; i <= TOP; ++i)
    for (int j = 0; j <= i; ++j)
      for (int k = 0; k < FN; ++k)
        g[i][k] = (g[i][k] + 1LL * f[i - j][k] * f[j][k] % MOD) % MOD;
  for (int i = 0; i <= TOP; ++i) fwt(g[i], -1, 0, FN);
  for (int i = 0; i < FN; ++i) cntor[i] = g[cnt1[i]][i];
}
void get_FibVal(int *a, int *b) {
  for (int i = 0; i < FN; ++i) a[i] = 1LL * b[i] * fib[i] % MOD;
}