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 = 1000000, maxs = 1 << 17;
const int mod = 1e9 + 7;
const long double Pi = acos(-1.0);
const double eps = 1e-7;
template <class T>
void read(T &x) {
  x = 0;
  int f = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    f |= (ch == '-');
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  x = f ? -x : x;
  return;
}
int n, s[maxn + 5], b[maxs + 5], cnt[maxs + 5];
int fib[maxs + 5], a[maxs + 5], c[maxs + 5];
int f[20][maxs + 5], num[maxs + 5];
inline int inc(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int dec(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
inline void FWTor(int *a, int maxx, int type) {
  for (int mid = 1; mid < maxx; mid <<= 1)
    for (int r = mid << 1, j = 0; j < maxx; j += r)
      for (int k = 0; k < mid; k++)
        a[j | k | mid] = inc(a[j | k | mid], 1ll * a[j | k] * type % mod);
}
inline void FWTand(int *a, int maxx, int type) {
  for (int mid = 1; mid < maxx; mid <<= 1)
    for (int r = mid << 1, j = 0; j < maxx; j += r)
      for (int k = 0; k < mid; k++)
        a[j | k] = inc(a[j | k], 1ll * a[j | k | mid] * type % mod);
}
inline void FWTxor(int *a, int maxx, int type) {
  for (int mid = 1; mid < maxx; mid <<= 1)
    for (int r = mid << 1, j = 0; j < maxx; j += r)
      for (int k = 0; k < mid; k++) {
        int x = a[j | k];
        int y = a[j | k | mid];
        a[j | k] = inc(x, y);
        a[j | k | mid] = dec(x, y);
        a[j | k] = 1ll * a[j | k] * type % mod;
        a[j | k | mid] = 1ll * a[j | k | mid] * type % mod;
      }
}
int main() {
  fib[1] = 1;
  for (int i = 2; i < maxs; i++) fib[i] = inc(fib[i - 1], fib[i - 2]);
  for (int i = 1; i <= maxs; i++) cnt[i] = cnt[i >> 1] + (i & 1);
  int lim = 17;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    a[s[i]]++;
    b[s[i]]++;
    c[s[i]]++;
  }
  for (int i = 1; i <= n; i++)
    if (a[s[i]]) {
      f[cnt[s[i]]][s[i]] = a[s[i]];
      a[s[i]] = 0;
    }
  for (int i = 0; i <= lim; i++) FWTor(f[i], maxs, 1);
  for (int i = 0; i <= lim; i++) {
    for (int j = 0; j < maxs; j++) num[j] = 0;
    for (int j = 0; j <= i; j++)
      for (int k = 0; k < maxs; k++)
        num[k] = inc(num[k], 1ll * f[j][k] * f[i - j][k] % mod);
    FWTor(num, maxs, mod - 1);
    for (int j = 0; j < maxs; j++)
      if (cnt[j] == i) a[j] = num[j];
  }
  FWTxor(c, maxs, 1);
  for (int i = 0; i < maxs; i++) c[i] = 1ll * c[i] * c[i] % mod;
  FWTxor(c, maxs, (mod + 1) >> 1);
  for (int i = 0; i < maxs; i++) {
    a[i] = 1ll * a[i] * fib[i] % mod;
    b[i] = 1ll * b[i] * fib[i] % mod;
    c[i] = 1ll * c[i] * fib[i] % mod;
  }
  FWTand(a, maxs, 1);
  FWTand(b, maxs, 1);
  FWTand(c, maxs, 1);
  for (int i = 0; i < maxs; i++) a[i] = 1ll * a[i] * b[i] % mod * c[i] % mod;
  FWTand(a, maxs, mod - 1);
  int ans = 0;
  for (int i = 0; i <= lim; i++) ans = inc(ans, a[1 << i]);
  printf("%d", ans);
  return 0;
}