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;
vector<long long> subset_sum_conv(vector<long long> A, vector<long long> B,
                                  int n) {
  int sz = 1 << n;
  assert(A.size() == sz);
  assert(B.size() == sz);
  vector<vector<long long>> FA(n + 1, vector<long long>(sz)), FB = FA, FC = FA;
  for (int m = 0; m < (1 << n); m++) {
    int popcnt = __builtin_popcount(m);
    FA[popcnt][m] = A[m];
    FB[popcnt][m] = B[m];
  }
  for (int popcnt = 0; popcnt <= n; popcnt++) {
    for (int i = 0; i < n; i++) {
      for (int m = 0; m < (1 << n); m++) {
        if ((m >> i) & 1) {
          FA[popcnt][m] += FA[popcnt][m ^ (1 << i)];
          FB[popcnt][m] += FB[popcnt][m ^ (1 << i)];
        }
      }
    }
  }
  for (int pa = 0; pa <= n; pa++) {
    for (int pb = 0; pa + pb <= n; pb++) {
      for (int m = 0; m < (1 << n); m++) {
        FC[pa + pb][m] += FA[pa][m] * FB[pb][m];
      }
    }
  }
  for (int popcnt = 0; popcnt <= n; popcnt++) {
    for (int i = 0; i < n; i++) {
      for (int m = 0; m < (1 << n); m++) {
        if ((m >> i) & 1) FC[popcnt][m] -= FC[popcnt][m ^ (1 << i)];
      }
    }
  }
  vector<long long> res(sz);
  for (int m = 0; m < (1 << n); m++) {
    int popcnt = __builtin_popcount(m);
    res[m] = FC[popcnt][m];
  }
  return res;
}
void FWHT(vector<long long> &p, bool inv) {
  int n = p.size();
  assert((n & (n - 1)) == 0);
  for (int len = 1; 2 * len <= n; len <<= 1) {
    for (int i = 0; i < n; i += len + len) {
      for (int j = 0; j < len; j++) {
        long long u = p[i + j], v = p[i + len + j];
        p[i + j] = u + v;
        p[i + len + j] = u - v;
      }
    }
  }
  if (inv)
    for (int i = 0; i < n; i++) p[i] /= n;
}
vector<long long> xor_conv(vector<long long> a, vector<long long> b) {
  int n = 1, sz = max(a.size(), b.size());
  while (n < sz) n *= 2;
  a.resize(n);
  b.resize(n);
  vector<long long> res(n, 0);
  FWHT(a, 0);
  FWHT(b, 0);
  for (int i = 0; i < n; i++) res[i] = a[i] * b[i];
  FWHT(res, 1);
  return res;
}
long long mod = 1e9 + 7;
vector<long long> and_conv(vector<long long> A, vector<long long> B, int n) {
  int sz = 1 << n;
  assert(A.size() == sz);
  assert(B.size() == sz);
  vector<long long> FA = A, FB = B;
  for (int i = 0; i < (1 << n); i++) {
    FA[i] %= mod;
    if (FA[i] < 0) FA[i] += mod;
    FB[i] %= mod;
    if (FB[i] < 0) FB[i] += mod;
  }
  for (int k = 0; k < n; k++) {
    for (int m = 0; m < (1 << n); m++) {
      if (!((m >> k) & 1)) {
        FA[m] += FA[m ^ (1 << k)];
        if (FA[m] >= mod) FA[m] -= mod;
        FB[m] += FB[m ^ (1 << k)];
        if (FB[m] >= mod) FB[m] -= mod;
      }
    }
  }
  for (int m = 0; m < (1 << n); m++) {
    FA[m] = FA[m] * FB[m] % mod;
  }
  for (int k = 0; k < n; k++) {
    for (int m = 0; m < (1 << n); m++) {
      if (!((m >> k) & 1)) {
        FA[m] -= FA[m ^ (1 << k)];
        if (FA[m] < 0) FA[m] += mod;
      }
    }
  }
  return FA;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> fib(1 << 17);
  fib[1] = 1;
  for (int i = 2; i < (1 << 17); i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  }
  vector<long long> f(1 << 17);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    f[x]++;
  }
  vector<long long> A = subset_sum_conv(f, f, 17);
  vector<long long> B = xor_conv(f, f);
  for (int i = 0; i < A.size(); i++) {
    A[i] %= mod;
    A[i] *= fib[i];
    A[i] %= mod;
    B[i] %= mod;
    B[i] *= fib[i];
    B[i] %= mod;
    f[i] %= mod;
    f[i] *= fib[i];
    f[i] %= mod;
  }
  vector<long long> C = and_conv(A, B, 17);
  C = and_conv(C, f, 17);
  long long ans = 0;
  for (int i = 1; i < (1 << 17); i++) {
    if ((i & (i - 1)) == 0) {
      ans += C[i];
      ans %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}