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;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
inline int fpm(long long b, int e, int m) {
  b %= m;
  long long t = 1;
  for (; e; e >>= 1, (b *= b) %= m)
    if (e & 1) (t *= b) %= m;
  return t;
}
const int maxn = 1000100;
const int maxbit = 17;
const int maxabs = 1 << maxbit;
inline void fwt(int *a, int n) {
  for (int i = 2; i <= n; i <<= 1)
    for (int j = 0; j < n; j += i) {
      for (int k = (0), k_end_ = (i >> 1); k < k_end_; ++k) {
        int tmpl = a[j + k], tmpr = a[j + (i >> 1) + k];
        a[j + k] = (tmpl + tmpr) % Mod;
        a[j + (i >> 1) + k] = (tmpl - tmpr) % Mod;
      }
    }
}
int n;
int a[maxn + 5];
int cntab[maxabs + 5];
int cntc[maxabs + 5];
int cntde[maxabs + 5];
int tmp[maxabs + 5];
int f[maxabs + 5];
int ret[maxn + 5];
int ans;
int main() {
  scanf("%d", &n);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
    scanf("%d", a + i);
    ++cntc[a[i]];
  }
  for (int i = (0), i_end_ = (maxabs); i < i_end_; ++i) {
    int j = i;
    cntab[i] = 0;
    while (1) {
      (cntab[i] += (long long)cntc[j] * cntc[i ^ j] % Mod) %= Mod;
      if (!j) break;
      j = (j - 1) & i;
    }
  }
  memcpy(tmp, cntc, sizeof tmp);
  fwt(tmp, maxabs);
  for (int i = (0), i_end_ = (maxabs); i < i_end_; ++i)
    tmp[i] = (long long)tmp[i] * tmp[i] % Mod;
  fwt(tmp, maxabs);
  int inv = fpm(maxabs, Mod - 2, Mod);
  for (int i = (0), i_end_ = (maxabs); i < i_end_; ++i)
    cntde[i] = (long long)tmp[i] * inv % Mod;
  f[0] = 0, f[1] = 1;
  for (int i = (2), i_end_ = (maxabs); i < i_end_; ++i)
    f[i] = (f[i - 1] + f[i - 2]) % Mod;
  for (int i = (0), i_end_ = (maxabs); i < i_end_; ++i) {
    cntab[i] = (long long)cntab[i] * f[i] % Mod;
    cntc[i] = (long long)cntc[i] * f[i] % Mod;
    cntde[i] = (long long)cntde[i] * f[i] % Mod;
  }
  for (int j = (0), j_end_ = (maxbit); j < j_end_; ++j)
    for (int i = (0), i_end_ = (maxabs); i < i_end_; ++i)
      if (!(i >> j & 1)) {
        (cntab[i] += cntab[i | (1 << j)]) %= Mod;
        (cntc[i] += cntc[i | (1 << j)]) %= Mod;
        (cntde[i] += cntde[i | (1 << j)]) %= Mod;
      }
  for (int i = (1), i_end_ = (maxabs); i < i_end_; ++i) {
    int val = (long long)cntab[i] * cntc[i] % Mod * cntde[i] % Mod;
    int cnt = __builtin_popcount(i);
    if (!(cnt & 1)) cnt = -cnt;
    (ans += (long long)val * cnt % Mod) %= Mod;
  }
  (ans += Mod) %= Mod;
  printf("%d\n", ans);
  return 0;
}