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;
const int inv2 = (mod + 1) / 2;
void fwt_xor(int len, int p[], int opt) {
  for (int i = 2; i <= len; i <<= 1) {
    for (int j = 0, h = i >> 1; j < len; j += i) {
      for (int k = j; k < j + h; ++k) {
        int x = p[k], y = p[k + h];
        p[k] = (x + y) % mod;
        p[k + h] = (x - y + mod) % mod;
        if (opt == -1)
          p[k] = (long long)p[k] * inv2 % mod,
          p[k + h] = (long long)p[k + h] * inv2 % mod;
      }
    }
  }
  return;
}
void fwt_and(int len, int p[], int opt) {
  for (int i = 2; i <= len; i <<= 1) {
    for (int j = 0, h = i >> 1; j < len; j += i) {
      for (int k = j; k < j + h; ++k) {
        int x = p[k], y = p[k + h];
        if (opt == 1)
          p[k] = (x + y) % mod;
        else
          p[k] = (x - y + mod) % mod;
      }
    }
  }
  return;
}
const int N = 17;
const int maxn = 1 << N;
int f[maxn];
int a[maxn], b[maxn], c[maxn];
int bin[maxn];
int dp[N + 1][maxn];
int cen[N + 1][maxn];
int main() {
  for (int i = (1); i < (maxn); ++i) bin[i] = bin[i - ((i) & (-(i)))] + 1;
  f[1] = 1;
  for (int i = (2); i < (maxn); ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  int n;
  cin >> n;
  for (int i = (1); i < (n + 1); ++i) {
    int x;
    scanf("%d", &x);
    a[x]++;
  }
  for (int i = (0); i < (maxn); ++i) b[i] = a[i];
  fwt_xor(maxn, b, 1);
  for (int i = (0); i < (maxn); ++i) b[i] = (long long)b[i] * b[i] % mod;
  fwt_xor(maxn, b, -1);
  for (int i = (0); i < (maxn); ++i) b[i] = (long long)b[i] * f[i] % mod;
  fwt_and(maxn, b, 1);
  for (int i = (0); i < (maxn); ++i) c[i] = (long long)a[i] * f[i] % mod;
  fwt_and(maxn, c, 1);
  for (int i = (0); i < (maxn); ++i) b[i] = (long long)b[i] * c[i] % mod;
  for (int i = (0); i < (maxn); ++i) cen[bin[i]][i] = a[i];
  for (int i = (0); i < (N + 1); ++i) fwt_xor(maxn, cen[i], 1);
  c[0] = 0;
  for (int i = 1; i <= N; ++i) {
    for (int cnt = 0; cnt <= i; ++cnt) {
      for (int j = (0); j < (maxn); ++j)
        dp[i][j] =
            (dp[i][j] + (long long)cen[cnt][j] * cen[i - cnt][j] % mod) % mod;
    }
    fwt_xor(maxn, dp[i], -1);
    for (int j = (1); j < (maxn); ++j)
      if (bin[j] == i) c[j] = dp[i][j];
  }
  for (int i = (0); i < (maxn); ++i) c[i] = (long long)c[i] * f[i] % mod;
  fwt_and(maxn, c, 1);
  for (int i = (0); i < (maxn); ++i) b[i] = (long long)b[i] * c[i] % mod;
  fwt_and(maxn, b, -1);
  int ans = 0;
  for (int i = (0); i < (N); ++i) ans = (ans + b[1 << i]) % mod;
  ans = (ans + mod) % mod;
  cout << ans << endl;
  return 0;
}