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 maxn = 1 << 18;
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
const int DFT = 1;
const int IDFT = -1;
int fa[maxn];
int fb[maxn];
int fc[maxn];
int cnt[maxn];
int f[maxn];
int h[18][maxn];
int g[18][maxn];
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
inline void inc(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
inline void dec(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
inline int mul(int a, int b) { return 1ll * a * b % mod; }
inline int mul(int a, int b, int c) { return 1ll * a * b % mod * c % mod; }
void FWT_OR(int *a, int len, int opt) {
  for (int i = 1; i < len; i <<= 1) {
    int step = i << 1;
    for (int j = 0; j < len; j += step) {
      for (int k = 0; k < i; k++) {
        if (opt == DFT)
          inc(a[i + j + k], a[j + k]);
        else
          dec(a[i + j + k], a[j + k]);
      }
    }
  }
}
void FWT_AND(int *a, int len, int opt) {
  for (int i = 1; i < len; i <<= 1) {
    int step = i << 1;
    for (int j = 0; j < len; j += step) {
      for (int k = 0; k < i; k++) {
        if (opt == DFT)
          inc(a[j + k], a[i + j + k]);
        else
          dec(a[j + k], a[i + j + k]);
      }
    }
  }
}
void FWT_XOR(int *a, int len, int opt) {
  for (int i = 1; i < len; i <<= 1) {
    int step = i << 1;
    for (int j = 0; j < len; j += step) {
      for (int k = 0; k < i; k++) {
        int x = a[j + k];
        int y = a[i + j + k];
        a[j + k] = add(x, y);
        a[i + j + k] = sub(x, y);
        if (opt == DFT) continue;
        a[j + k] = mul(a[j + k], inv2);
        a[i + j + k] = mul(a[i + j + k], inv2);
      }
    }
  }
}
int main(void) {
  int len = 1 << 18;
  cnt[0] = 0;
  for (int i = 1; i < len; i++) cnt[i] = cnt[i >> 1] + (i & 1);
  f[0] = 0;
  f[1] = 1;
  for (int i = 2; i < len; i++) f[i] = add(f[i - 1], f[i - 2]);
  int maxi = 0;
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    fa[x]++;
    fb[x]++;
    fc[x]++;
    g[cnt[x]][x]++;
    maxi = max(maxi, x);
  }
  len = 1;
  int bct = 0;
  while (len <= maxi) len <<= 1, bct++;
  for (int i = 0; i <= bct; i++) FWT_OR(g[i], len, DFT);
  for (int i = 0; i <= bct; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < len; k++) {
        h[i][k] = add(h[i][k], mul(g[j][k], g[i - j][k]));
      }
    }
    FWT_OR(h[i], len, IDFT);
  }
  FWT_XOR(fc, len, DFT);
  for (int i = 0; i < len; i++) fc[i] = mul(fc[i], fc[i]);
  FWT_XOR(fc, len, IDFT);
  for (int i = 0; i < len; i++) {
    fa[i] = mul(h[cnt[i]][i], f[i]);
    fb[i] = mul(fb[i], f[i]);
    fc[i] = mul(fc[i], f[i]);
  }
  FWT_AND(fa, len, DFT);
  FWT_AND(fb, len, DFT);
  FWT_AND(fc, len, DFT);
  for (int i = 0; i < len; i++) fa[i] = mul(fa[i], fb[i], fc[i]);
  FWT_AND(fa, len, IDFT);
  int res = 0;
  for (int i = 0; i <= bct; i++) {
    res = add(res, fa[1 << i]);
  }
  printf("%d\n", res);
  return 0;
}