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 int64_t maxn = 1 << 17, mod = 1e9 + 7;
int64_t A[maxn], B[maxn], C[maxn], F[maxn];
void xor_fft(int64_t *in, int64_t *out, int64_t n) {
  if (n == 1) {
    *out = *in;
    return;
  }
  n /= 2;
  xor_fft(in, out, n);
  xor_fft(in + n, out + n, n);
  for (int64_t i = 0; i < n; i++) {
    out[i] = out[i] + out[i + n];
    out[i + n] = out[i] - 2 * out[i + n] + 2 * mod;
    out[i] %= mod;
    out[i + n] %= mod;
  }
}
int64_t AA[maxn];
int64_t bpow(int64_t x, int64_t n) {
  return n ? n % 2 ? x * bpow(x, n - 1) % mod : bpow(x * x % mod, n / 2) : 1;
}
void xor_multiply(int64_t *a, int64_t *c) {
  xor_fft(a, AA, maxn);
  for (int64_t i = 0; i < maxn; i++) {
    AA[i] *= AA[i];
    AA[i] %= mod;
  }
  xor_fft(AA, c, maxn);
  int64_t inv = bpow(maxn, mod - 2);
  for (int64_t i = 0; i < maxn; i++) {
    c[i] *= inv;
    c[i] %= mod;
  }
}
void transform(int64_t *from, int64_t *to) {
  if (to - from == 1) return;
  int64_t *mid = from + (to - from) / 2;
  transform(from, mid);
  transform(mid, to);
  for (int64_t i = 0; i < mid - from; i++) {
    *(from + i) += *(mid + i);
    *(from + i) %= mod;
  }
}
void inverse(int64_t *from, int64_t *to) {
  if (to - from == 1) return;
  int64_t *mid = from + (to - from) / 2;
  inverse(from, mid);
  inverse(mid, to);
  for (int64_t i = 0; i < mid - from; i++) {
    *(from + i) -= *(mid + i) - mod;
    *(from + i) %= mod;
  }
}
void and_multiply(int64_t *A, int64_t *B, int64_t *C) {
  transform(A, A + maxn);
  transform(B, B + maxn);
  transform(C, C + maxn);
  for (int64_t i = 0; i < maxn; i++) {
    A[i] = A[i] * B[i] % mod * C[i] % mod;
  }
  inverse(A, A + maxn);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  F[0] = 0;
  F[1] = 1;
  for (int64_t i = 2; i < maxn; i++) {
    F[i] = F[i - 1] + F[i - 2];
    F[i] %= mod;
  }
  int64_t n;
  cin >> n;
  int64_t a[n];
  for (int64_t i = 0; i < n; i++) {
    cin >> a[i];
    B[a[i]]++;
  }
  for (int64_t mask = 0; mask < maxn; mask++) {
    for (int64_t i = mask;; i = (i - 1) & mask) {
      A[mask] += B[i] * B[mask ^ i];
      A[mask] %= mod;
      if (i == 0) {
        break;
      }
    }
  }
  xor_multiply(B, C);
  for (int64_t i = 0; i < maxn; i++) {
    A[i] *= F[i];
    B[i] *= F[i];
    C[i] *= F[i];
    A[i] %= mod;
    B[i] %= mod;
    C[i] %= mod;
  }
  and_multiply(A, B, C);
  int64_t ans = 0;
  for (int64_t i = 0; i < 17; i++) {
    ans += A[1 << i];
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}