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;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - 48;
    c = getchar();
  }
  return x * f;
}
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
long long power(long long x, long long k) {
  long long ret = 1;
  if (x == 1) return 1;
  for (; k; k >>= 1, x = x * x % mod)
    if (k & 1) ret = ret * x % mod;
  return ret;
}
int getbit(int x) {
  int ret = 0;
  for (; x; x -= x & -x) ret++;
  return ret;
}
void Or(long long *f, int n, int x) {
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += (k << 1)) {
      for (int j = 0; j < k; j++) {
        f[i + j + k] = (f[i + j + k] + f[i + j] * x + mod) % mod;
      }
    }
  }
}
void And(long long *f, int n, int x) {
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += (k << 1)) {
      for (int j = 0; j < k; j++) {
        f[i + j] = (f[i + j] + f[i + j + k] * x + mod) % mod;
      }
    }
  }
}
void Xor(long long *f, int n, int x) {
  for (int k = 1; k < n; k <<= 1) {
    for (int i = 0; i < n; i += (k << 1)) {
      for (int j = 0; j < k; j++) {
        long long u = f[i + j], v = f[i + j + k];
        f[i + j] = (u + v) * x % mod;
        f[i + j + k] = (u - v + mod) * x % mod;
      }
    }
  }
}
long long c[1 << 18], c1[1 << 18], c2[1 << 18];
long long f[1 << 18];
long long t[18][1 << 18], g[18][1 << 18], bit[1 << 18];
int main() {
  int n = read();
  for (int i = 1; i <= n; i++) c[read()]++;
  n = 17;
  int len = 1 << n;
  f[0] = 0;
  f[1] = 1;
  for (int s = 2; s < len; s++) f[s] = (f[s - 1] + f[s - 2]) % mod;
  for (int s = 0; s < len; s++) {
    bit[s] = getbit(s);
    g[bit[s]][s] = c[s];
  }
  for (int i = 0; i <= n; i++) Or(g[i], len, 1);
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < len; k++) {
        t[i][k] = (t[i][k] + g[j][k] * g[i - j][k]) % mod;
      }
    }
  }
  for (int i = 0; i <= n; i++) Or(t[i], len, -1);
  for (int k = 0; k < len; k++) c1[k] = t[bit[k]][k] * f[k] % mod;
  Xor(c, len, 1);
  for (int k = 0; k < len; k++) c2[k] = c[k] * c[k] % mod;
  Xor(c, len, power(2, mod - 2));
  Xor(c2, len, power(2, mod - 2));
  for (int k = 0; k < len; k++) c2[k] = c2[k] * f[k] % mod;
  for (int k = 0; k < len; k++) c[k] = c[k] * f[k] % mod;
  And(c, len, 1);
  And(c1, len, 1);
  And(c2, len, 1);
  for (int k = 0; k < len; k++) {
    c[k] = c[k] * c1[k] % mod;
    c[k] = c[k] * c2[k] % mod;
  }
  And(c, len, -1);
  long long ans = 0;
  for (int i = 0; i <= n; i++) {
    ans = (ans + c[1 << i]) % mod;
  }
  printf("%lld\n", (ans + mod) % mod);
  return 0;
}