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 <class T>
ostream& operator<<(ostream& stream, const vector<T> v) {
  stream << "[ ";
  for (int i = 0; i < (int)v.size(); i++) stream << v[i] << " ";
  stream << "]";
  return stream;
}
long long fpow(long long x, long long p, long long m) {
  long long r = 1;
  for (; p; p >>= 1) {
    if (p & 1) r = r * x % m;
    x = x * x % m;
  }
  return r;
}
long long inv(long long a, long long b) {
  return a < 2 ? a : ((a - inv(b % a, a)) * b + 1) / a % b;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const long long mod = 1000000007;
const int lg = 17, sz = (1 << 17), i2 = 500000004;
vector<long long> a(sz);
int N;
long long f[sz];
vector<long long> conv(vector<long long>& a, vector<long long>& b, int tp) {
  int len, i, k;
  vector<long long> c;
  c.insert(c.end(), (a).begin(), (a).end());
  c.insert(c.end(), (b).begin(), (b).end());
  for (len = sz; len > 1; len >>= 1) {
    for (i = 0; i < 2 * sz; i += 2 * len) {
      for (k = 0; k < len / 2; k++) {
        long long a = c[i + k], na = c[i + len / 2 + k];
        long long b = c[i + len + k], nb = c[i + 3 * len / 2 + k];
        if (tp == 0) {
          c[i + k] = (a + na) % mod;
          c[i + len / 2 + k] = (b + nb) % mod;
          c[i + len + k] = (a - na + mod) % mod,
                      c[i + 3 * len / 2 + k] = (b - nb + mod) % mod;
        } else {
          c[i + k] = (a + na) % mod;
          c[i + len / 2 + k] = (b + nb) % mod;
          c[i + len + k] = na, c[i + 3 * len / 2 + k] = nb;
        }
      }
    }
  }
  for (i = 0; i < 2 * sz; i += 2) c[i] = (c[i] * c[i + 1]) % mod;
  for (len = 2; len <= sz; len <<= 1) {
    for (i = 0; i < 2 * sz; i += 2 * len) {
      for (k = 0; k < len / 2; k++) {
        long long a = c[i + k], b = c[i + len + k];
        if (tp == 0) {
          c[i + k] = (a + b) * i2 % mod;
          c[i + len / 2 + k] = (a - b + mod) * i2 % mod;
        } else {
          c[i + k] = (a - b + mod) % mod;
          c[i + len / 2 + k] = b;
        }
      }
    }
  }
  c.resize(sz);
  return c;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  int i;
  a.resize(sz);
  for (i = 1; i <= N; i++) {
    int x;
    cin >> x;
    a[x]++;
  }
  f[0] = 0, f[1] = 1;
  for (i = 2; i < sz; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
  }
  vector<long long> A(sz), B(sz), C(sz);
  B = a;
  {
    vector<long long> x = a, y = a;
    C = conv(x, y, 0);
  }
  for (i = 0; i < sz; i++) {
    int mask = sz - 1 - i;
    int cr = mask;
    do {
      A[i | cr] = (A[i | cr] + a[i] * a[cr]) % mod;
      cr = mask & (cr - 1);
    } while (cr != mask);
  }
  for (i = 0; i < sz; i++) {
    A[i] = A[i] * f[i] % mod;
    B[i] = B[i] * f[i] % mod;
    C[i] = C[i] * f[i] % mod;
  }
  vector<long long> x, y;
  x = conv(A, B, 1);
  y = conv(x, C, 1);
  long long res = 0;
  for (i = 0; i < lg; i++) res = (res + y[(1 << i)]) % mod;
  cout << res << "\n";
  return 0;
}