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 maxn = 1 << 17;
const long long md = 1e9 + 7;
const long long mxi = 742744451ll;
long long fib[maxn];
int a[maxn];
long long cnt[maxn];
long long f[maxn];
long long g[maxn];
long long A[maxn];
long long B[maxn];
long long C[maxn];
void walsh(int l, int r) {
  int mid = (l + r) >> 1;
  for (int i = l; i < mid; i++) {
    int u = g[i], v = g[mid + i - l];
    g[i] = (u + v) % md;
    g[mid + i - l] = (u + md - v) % md;
  }
  if (r - l <= 2) return;
  walsh(l, mid);
  walsh(mid, r);
}
void andtrans(long long* arr, int l, int r, bool inv) {
  int mid = (l + r) >> 1;
  for (int i = l; i < mid; i++) {
    int u = arr[i], v = arr[mid + i - l];
    if (!inv) {
      arr[i] = v;
      arr[mid + i - l] = (u + v) % md;
    } else {
      arr[i] = (md - u + v) % md;
      arr[mid + i - l] = u;
    }
  }
  if (r - l <= 2) return;
  andtrans(arr, l, mid, inv);
  andtrans(arr, mid, r, inv);
}
void trans() {
  andtrans(A, 0, maxn, false);
  andtrans(B, 0, maxn, false);
  for (int i = 0; i < maxn; i++) {
    C[i] = (A[i] * B[i]) % md;
  }
  andtrans(C, 0, maxn, true);
  for (int i = 0; i < maxn; i++) {
    if (C[i] >= 0)
      continue;
    else
      C[i] = (md - (-C[i]) % md);
  }
}
int main() {
  int n;
  scanf("%d", &n);
  fib[0] = 0;
  fib[1] = 1;
  fill(g, g + maxn, 0);
  fill(cnt, cnt + maxn, 0);
  for (int i = 2; i < maxn; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % md;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    cnt[x]++;
    g[x]++;
  }
  for (int i = 0; i < maxn; i++) {
    f[i] = 0;
    for (int j = i; j >= 0; j = (j - 1) & i) {
      f[i] = (f[i] + cnt[j] * cnt[i - j]) % md;
      if (j == 0) break;
    }
  }
  walsh(0, maxn);
  for (int i = 0; i < maxn; i++) g[i] = (g[i] * g[i]) % md;
  walsh(0, maxn);
  for (int i = 0; i < maxn; i++) g[i] = (g[i] * mxi) % md;
  for (int i = 0; i < maxn; i++) {
    f[i] = (f[i] * fib[i]) % md;
    g[i] = (g[i] * fib[i]) % md;
    cnt[i] = (cnt[i] * fib[i]) % md;
  }
  for (int i = 0; i < maxn; i++) {
    A[i] = f[i];
    B[i] = g[i];
    C[i] = 0;
  }
  trans();
  for (int i = 0; i < maxn; i++) {
    A[i] = C[i];
    B[i] = cnt[i];
    C[i] = 0;
  }
  trans();
  long long ans = 0;
  for (int i = 0; (1 << i) < maxn; i++) {
    ans = (ans + C[1 << i]) % md;
  }
  cout << ans << endl;
}