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 long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
template <class num>
inline void rd(num &x) {
  char c;
  while (isspace(c = getchar()))
    ;
  bool neg = false;
  if (!isdigit(c))
    neg = (c == '-'), x = 0;
  else
    x = c - '0';
  while (isdigit(c = getchar())) x = (x << 3) + (x << 1) + c - '0';
  if (neg) x = -x;
}
void tf_xor(long long a[], int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  tf_xor(a, l, m);
  tf_xor(a, m + 1, r);
  for (int i = l; i <= m; i++) {
    int j = (m + 1 + (i - l));
    long long A = a[i];
    long long B = a[j];
    a[i] = mod(A + B);
    a[j] = mod(A - B + modn);
  }
}
void itf_xor(long long a[], int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  for (int i = l; i <= m; i++) {
    int j = (m + 1 + (i - l));
    long long A = a[i];
    long long B = a[j];
    a[i] = mod((A + B) * ((modn + 1) / 2ll));
    a[j] = mod((A - B + modn) * ((modn + 1) / 2ll));
  }
  itf_xor(a, l, m);
  itf_xor(a, m + 1, r);
}
void tf_and(long long a[], int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  tf_and(a, l, m);
  tf_and(a, m + 1, r);
  for (int i = l; i <= m; i++) {
    int j = (m + 1 + (i - l));
    long long A = a[i];
    long long B = a[j];
    a[i] = mod(A + B);
  }
}
void itf_and(long long a[], int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  for (int i = l; i <= m; i++) {
    int j = (m + 1 + (i - l));
    long long A = a[i];
    long long B = a[j];
    a[i] = mod(A - B + modn);
  }
  itf_and(a, l, m);
  itf_and(a, m + 1, r);
}
const int K = 17;
void tf_dor(int k, long long a[], long long b[], int l, int r) {
  if (l == r) return (void)(b[l] = a[l] * (__builtin_popcount(l) == k));
  int m = (l + r) / 2;
  tf_dor(k, a, b, l, m);
  tf_dor(k, a, b, m + 1, r);
  for (int i = l; i <= m; i++)
    b[m + 1 + (i - l)] = mod(b[m + 1 + (i - l)] + b[i]);
}
void tf_dor(int k, long long a[], long long b[K + 1][1 << K]) {
  for (int i = 0; i <= k; i++) tf_dor(i, a, b[i], 0, (1 << k) - 1);
}
void conv(int k, long long a[K + 1][1 << K], long long b[K + 1][1 << K],
          long long c[K + 1][1 << K]) {
  for (int j = 0; j <= k; j++)
    for (int i = 0; i < (1 << k); i++) {
      c[j][i] = 0;
      for (int g = 0; g <= j; g++)
        c[j][i] = mod(c[j][i] + a[g][i] * b[j - g][i]);
    }
}
void itf_dor(long long a[], int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  for (int i = l; i <= m; i++)
    a[m + 1 + (i - l)] = mod(a[m + 1 + (i - l)] - a[i] + modn);
  itf_dor(a, l, m);
  itf_dor(a, m + 1, r);
}
void itf_dor(int k, long long a[K + 1][1 << K], long long b[]) {
  for (int j = 0; j <= k; j++) {
    itf_dor(a[j], 0, (1 << k) - 1);
    for (int i = 0; i < (1 << k); i++)
      if (__builtin_popcount(i) == j) b[i] = a[j][i];
  }
}
long long base[1 << K];
long long a_[K + 1][1 << K], ans[K + 1][1 << K];
long long p[3][1 << K];
long long f[1 << K];
int main() {
  int n, i, j;
  rd(n);
  while (n--) {
    int x;
    rd(x);
    base[x]++;
  }
  tf_dor(K, base, a_);
  conv(K, a_, a_, ans);
  itf_dor(K, ans, p[0]);
  for (i = 0; i < (1 << K); i++) p[1][i] = base[i];
  for (i = 0; i < (1 << K); i++) p[2][i] = base[i];
  tf_xor(p[2], 0, (1 << K) - 1);
  for (i = 0; i < (1 << K); i++) p[2][i] = mod(p[2][i] * p[2][i]);
  itf_xor(p[2], 0, (1 << K) - 1);
  f[0] = 0;
  f[1] = 1;
  for (i = 2; i < (1 << K); i++) f[i] = mod(f[i - 1] + f[i - 2]);
  for (j = 0; j < 3; j++) {
    for (i = 0; i < (1 << K); i++) p[j][i] = mod(p[j][i] * f[i]);
    tf_and(p[j], 0, (1 << K) - 1);
    if (j)
      for (i = 0; i < (1 << K); i++) p[0][i] = mod(p[0][i] * p[j][i]);
  }
  itf_and(p[0], 0, (1 << K) - 1);
  long long ans = 0;
  for (i = 0; i < K; i++) ans = mod(ans + p[0][1 << i]);
  printf("%lld\n", ans);
}