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 int mod = 1000000007, N = 17;
int n, ans;
int f[200010], g[200010], h[200010], a[200010], c[200010][20], fib[200010],
    cnt[200010], tmp[40];
void update(int &i, int x) { i = (i + x) - (i + x >= mod ? mod : 0); }
int fpow(int i, int j) {
  int ret = 1;
  for (; j; i = (long long)i * i % mod, j /= 2)
    if (j & 1) ret = (long long)ret * i % mod;
  return ret;
}
int main() {
  int i, j, k, x, y;
  fib[0] = 0;
  fib[1] = 1;
  for (i = 2; i <= (1 << N); i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  for (i = 1; i < (1 << N); i++) cnt[i] = cnt[i - (i & (-i))] + 1;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    a[x]++;
  }
  for (i = 0; i < (1 << N); i++) c[i][cnt[i]] = a[i];
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      for (k = 0; k <= N; k++) update(c[j | (1 << i)][k], c[j][k]);
    }
  for (i = 0; i < (1 << N); i++) {
    memset(tmp, 0, sizeof(tmp));
    for (j = 0; j <= N; j++)
      for (k = 0; j + k <= N; k++)
        update(tmp[j + k], (long long)c[i][j] * c[i][k] % mod);
    for (j = 0; j <= N; j++) c[i][j] = tmp[j];
  }
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      for (k = 0; k <= N; k++) update(c[j | (1 << i)][k], mod - c[j][k]);
    }
  for (i = 0; i < (1 << N); i++) f[i] = (long long)fib[i] * c[i][cnt[i]] % mod;
  for (i = 0; i < (1 << N); i++) g[i] = a[i];
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      x = g[j];
      y = g[j | (1 << i)];
      g[j] = (x + y) % mod;
      g[j | (1 << i)] = (x + mod - y) % mod;
    }
  for (i = 0; i < (1 << N); i++) g[i] = (long long)g[i] * g[i] % mod;
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      x = g[j];
      y = g[j | (1 << i)];
      g[j] = (x + y) % mod;
      g[j | (1 << i)] = (x + mod - y) % mod;
    }
  x = fpow(1 << N, mod - 2);
  for (i = 0; i < (1 << N); i++) g[i] = (long long)g[i] * x % mod;
  for (i = 0; i < (1 << N); i++) g[i] = (long long)fib[i] * g[i] % mod;
  for (i = 0; i < (1 << N); i++) h[i] = (long long)fib[i] * a[i] % mod;
  for (i = 0; i < (1 << (N - 1)); i++) {
    x = i ^ ((1 << N) - 1);
    swap(f[i], f[x]);
    swap(g[i], g[x]);
    swap(h[i], h[x]);
  }
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      update(f[j | (1 << i)], f[j]);
      update(g[j | (1 << i)], g[j]);
      update(h[j | (1 << i)], h[j]);
    }
  for (i = 0; i < (1 << N); i++)
    f[i] = (long long)f[i] * g[i] % mod * h[i] % mod;
  for (i = 0; i < N; i++)
    for (j = 0; j < (1 << N); j++) {
      if (j & (1 << i)) continue;
      update(f[j | (1 << i)], mod - f[j]);
    }
  for (i = 0; i < (1 << (N - 1)); i++) {
    x = i ^ ((1 << N) - 1);
    swap(f[i], f[x]);
  }
  for (i = 0; i < N; i++) update(ans, f[(1 << i)]);
  printf("%d\n", ans);
  return 0;
}