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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int B = 17;
const int N = 1 << B;
const long long int M = (int)1e9 + 7;
const long long int inv2 = (int)5e8 + 4;
int n;
long long int cnt[N], fib[N], ab[N], Xor[N], And[N];
void transform_xor(long long int x[], bool inv = 0) {
  for (int mid = 1, i = 2; i <= N; mid = i, i <<= 1)
    for (int j = 0, lo = 0; lo < N; j + 1 == mid ? (lo += i, j = 0) : ++j) {
      long long int tw1 = x[lo + j], tw2 = x[lo + j + mid];
      if (inv) {
        x[lo + j] = (tw1 + tw2) % M * inv2 % M;
        x[lo + j + mid] = (tw1 - tw2 + M) % M * inv2 % M;
      } else {
        x[lo + j] = tw1 + tw2;
        if (x[lo + j] >= M) x[lo + j] -= M;
        x[lo + j + mid] = tw1 - tw2;
        if (x[lo + j + mid] < 0) x[lo + j + mid] += M;
      }
    }
}
void transform_and(long long int p[], bool inv = 0) {
  for (int len = 1; (len << 1) <= N; len <<= 1)
    for (int i = 0; i < N; i += (len << 1))
      for (int j = 0; j < len; ++j) {
        long long int tw1 = p[i + j];
        long long int tw2 = p[i + len + j];
        if (!inv) {
          p[i + j] = tw2;
          p[i + len + j] = tw1 + tw2;
          if (p[i + len + j] >= M) p[i + len + j] -= M;
        } else {
          p[i + j] = tw2 - tw1;
          if (p[i + j] < 0) p[i + j] += M;
          p[i + len + j] = tw1;
        }
      }
}
void solve(std::istream &in, std::ostream &out) {
  fib[0] = 0, fib[1] = 1;
  for (int i = 2; i < N; ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= M) fib[i] -= M;
  }
  in >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    in >> x;
    ++cnt[x];
  }
  for (int i = 0; i < N; ++i) {
    ab[i] = 0;
    for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
      ab[i] += cnt[j] * cnt[j ^ i] % M;
      if (ab[i] >= M) ab[i] -= M;
    }
    if (cnt[0] && cnt[i]) {
      ab[i] += cnt[0] * cnt[i] * 2 % M;
      if (ab[i] >= M) ab[i] -= M;
    }
  }
  memcpy(Xor, cnt, sizeof cnt);
  transform_xor(Xor);
  for (int i = 0; i < N; ++i) Xor[i] = Xor[i] * Xor[i] % M;
  transform_xor(Xor, 1);
  for (int i = 0; i < N; ++i)
    Xor[i] = Xor[i] * fib[i] % M, ab[i] = ab[i] * fib[i] % M,
    cnt[i] = cnt[i] * fib[i] % M;
  transform_and(Xor);
  transform_and(ab);
  transform_and(cnt);
  for (int i = 0; i < N; ++i) And[i] = Xor[i] * ab[i] % M * cnt[i] % M;
  transform_and(And, 1);
  long long int ans = 0;
  for (int i = 1; i < N; i <<= 1) ans = (ans + And[i]) % M;
  out << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve(cin, cout);
  return 0;
}