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>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const long long mod = 1000000007;
namespace and_convolution {
const int size = 1 << 17;
void MOD(long long& v) {
  v %= mod;
  v += mod;
  v %= mod;
}
void transform(long long p[]) {
  for (int len = 1; 2 * len <= size; len <<= 1) {
    for (int i = 0; i < size; i += (2 * len)) {
      for (int j = 0; j < len; j++) {
        long long u = p[i + j], v = p[i + j + len];
        p[i + j] = v;
        p[i + j + len] = u + v;
        MOD(p[i + j + len]);
      }
    }
  }
}
void inverse(long long p[]) {
  for (int len = 1; 2 * len <= size; len <<= 1) {
    for (int i = 0; i < size; i += (2 * len)) {
      for (int j = 0; j < len; j++) {
        long long u = p[i + j], v = p[i + j + len];
        p[i + j] = mod - u + v;
        p[i + j + len] = u;
        MOD(p[i + j]);
      }
    }
  }
}
};  // namespace and_convolution
namespace xor_convolution {
const int size = 1 << 17;
void transform(long long p[]) {
  for (int len = 1; 2 * len <= size; len <<= 1) {
    for (int i = 0; i < size; i += (2 * len)) {
      for (int j = 0; j < len; j++) {
        long long u = p[i + j], v = p[i + j + len];
        p[i + j] = u + v;
        p[i + j + len] = u - v;
      }
    }
  }
}
};  // namespace xor_convolution
const int maxn = 1000100;
const int maxb = 1 << 17;
int arr[maxn];
long long occ[maxb];
long long xor_conv[maxb];
long long and_conv[maxb];
long long or_conv[maxb];
long long fib[maxb];
long long ofib[maxb];
long long odb[maxb];
long long exponentiation(long long A, long long B, long long MOD) {
  long long ans = 1;
  for (; B; A = (A * A) % MOD, B >>= 1)
    if (B & 1) ans = (ans * A) % MOD;
  return ans;
}
int main() {
  fib[0] = 0;
  fib[1] = 1;
  for (int e = 2; e < maxb; e++) fib[e] = (fib[e - 1] + fib[e - 2]) % mod;
  int n;
  scanf("%d", &n);
  for (int e = 0; e < n; e++) scanf("%d", arr + e);
  for (int e = 0; e < n; e++) xor_conv[arr[e]]++;
  xor_convolution::transform(xor_conv);
  for (int e = 0; e < maxb; e++) xor_conv[e] *= xor_conv[e], xor_conv[e] %= mod;
  xor_convolution::transform(xor_conv);
  for (int e = 0; e < maxb; e++) xor_conv[e] %= mod;
  for (int e = 0; e < maxb; e++)
    xor_conv[e] *= exponentiation(maxb, mod - 2, mod);
  for (int e = 0; e < maxb; e++) xor_conv[e] %= mod;
  for (int e = 0; e < n; e++) occ[arr[e]]++;
  for (int e = 0; e < maxb; e++) xor_conv[e] = xor_conv[e] * fib[e] % mod;
  for (int e = 0; e < maxb; e++) ofib[e] = occ[e] * fib[e] % mod;
  and_convolution::transform(ofib);
  and_convolution::transform(xor_conv);
  for (int e = 0; e < maxb; e++) ofib[e] = xor_conv[e] * ofib[e] % mod;
  and_convolution::inverse(ofib);
  int N = 17;
  for (int E = 0; E < (1 << N); E++) {
    int counter = ((1 << N) - 1) ^ E;
    if (E) {
      odb[counter | E] += occ[counter] * occ[E] % mod;
      if (odb[counter | E] >= mod) odb[counter | E] -= mod;
    }
    for (int F = E & (E - 1); F; F = E & (F - 1)) {
      odb[counter | F] += occ[counter] * occ[F] % mod;
      if (odb[counter | F] >= mod) odb[counter | F] -= mod;
    }
    odb[counter] += occ[counter] * occ[0] % mod;
    if (odb[counter] >= mod) odb[counter] -= mod;
  }
  for (int e = 0; e < maxb; e++) odb[e] = odb[e] * fib[e] % mod;
  and_convolution::transform(ofib);
  and_convolution::transform(odb);
  for (int e = 0; e < maxb; e++) ofib[e] = ofib[e] * odb[e] % mod;
  and_convolution::inverse(ofib);
  long long ans = 0;
  for (int e = 1; e < maxb; e++) {
    int v = e & -e;
    if (v == e) {
      ans += ofib[e];
      ans %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}