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 = 1e9 + 7, inv2 = 5e8 + 4;
int n, m, mx;
int a[1000005], f[300005];
int p1[300005], p2[300005], p3[300005], ans[300005], size[300005];
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x * f;
}
void subset_conv(int *ret, int *a, int *b) {
  static int suma[300005][20], sumb[300005][20], sum[300005][20];
  for (int i = 0; i < (1 << n); i++) size[i] = size[i >> 1] + (i & 1);
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j <= n; j++)
      (j == size[i]) ? (suma[i][j] = a[i], sumb[i][j] = b[i])
                     : (suma[i][j] = sumb[i][j] = 0);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < (1 << n); j++)
      if (j >> i & 1)
        for (int k = 0; k <= n; k++) {
          suma[j][k] = (suma[j][k] + suma[j ^ (1 << i)][k]) % mod;
          sumb[j][k] = (sumb[j][k] + sumb[j ^ (1 << i)][k]) % mod;
        }
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j <= n; j++) {
      sum[i][j] = 0;
      for (int k = 0; k <= j; k++)
        sum[i][j] = (sum[i][j] + 1ll * suma[i][k] * sumb[i][j - k]) % mod;
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < (1 << n); j++)
      if (j >> i & 1)
        for (int k = 0; k <= n; k++)
          sum[j][k] = (sum[j][k] - sum[j ^ (1 << i)][k]) % mod;
  for (int i = 0; i < (1 << n); i++) ret[i] = sum[i][size[i]];
}
void xor_fwt(int *a, int op) {
  for (int i = 2; i <= (1 << n); i <<= 1)
    for (int j = 0; j < (1 << n); j += i)
      for (int k = 0; k < (i >> 1); k++) {
        int x = a[j + k], y = a[j + k + (i >> 1)];
        if (op)
          a[j + k] = (x + y) % mod, a[j + k + (i >> 1)] = (x - y) % mod;
        else
          a[j + k] = 1ll * (x + y) * inv2 % mod,
                a[j + k + (i >> 1)] = 1ll * (x - y) * inv2 % mod;
      }
}
void xor_conv(int *ret, int *a, int *b) {
  static int ta[300005], tb[300005];
  for (int i = 0; i < (1 << n); i++) ta[i] = a[i], tb[i] = b[i];
  xor_fwt(ta, 1), xor_fwt(tb, 1);
  for (int i = 0; i < (1 << n); i++) ret[i] = 1ll * ta[i] * tb[i] % mod;
  xor_fwt(ret, 0);
}
void and_fwt(int *a, int op) {
  for (int i = 2; i <= (1 << n); i <<= 1)
    for (int j = 0; j < (1 << n); j += i)
      for (int k = 0; k < (i >> 1); k++) {
        int x = a[j + k], y = a[j + k + (i >> 1)];
        if (op)
          a[j + k] = (x + y) % mod, a[j + k + (i >> 1)] = y;
        else
          a[j + k] = (x - y) % mod, a[j + k + (i >> 1)] = y;
      }
}
void and_conv(int *ret, int *a, int *b) {
  static int ta[300005], tb[300005];
  for (int i = 0; i < (1 << n); i++) ta[i] = a[i], tb[i] = b[i];
  and_fwt(ta, 1), and_fwt(tb, 1);
  for (int i = 0; i < (1 << n); i++) ret[i] = 1ll * ta[i] * tb[i] % mod;
  and_fwt(ret, 0);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), mx = max(mx, a[i]);
  for (int i = 1; i <= n; i++) ++p2[a[i]];
  n = 32 - __builtin_clz(mx);
  f[0] = 0, f[1] = 1;
  for (int i = 2; i < (1 << n); i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  subset_conv(p1, p2, p2), xor_conv(p3, p2, p2);
  for (int i = 0; i < (1 << n); i++) p1[i] = 1ll * p1[i] * f[i] % mod;
  for (int i = 0; i < (1 << n); i++) p2[i] = 1ll * p2[i] * f[i] % mod;
  for (int i = 0; i < (1 << n); i++) p3[i] = 1ll * p3[i] * f[i] % mod;
  and_conv(ans, p1, p2), and_conv(ans, ans, p3);
  int res = 0;
  for (int i = 0; i < n; i++) res = (res + ans[1 << i]) % mod;
  cout << (res + mod) % mod << endl;
  return 0;
}