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;
namespace SHENZHEBEI {
const int L = 2333333;
char SZB[L], *S = SZB, *T = SZB;
inline char gc() {
  if (S == T) {
    T = (S = SZB) + fread(SZB, 1, L, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
inline long long read() {
  long long x = 0, f = 1;
  char ch = gc();
  for (; !isdigit(ch); ch = gc())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = gc()) x = x * 10 - 48 + ch;
  return x * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline char readchar() {
  char ch = gc();
  for (; isspace(ch); ch = gc())
    ;
  return ch;
}
inline long long readstr(char *s) {
  char ch = gc();
  int cur = 0;
  for (; isspace(ch); ch = gc())
    ;
  for (; !isspace(ch); ch = gc()) s[cur++] = ch;
  s[cur] = '\0';
  return cur;
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
}  // namespace SHENZHEBEI
using namespace SHENZHEBEI;
const long long N = 2100000, mod = 1e9 + 7, mo = 1e9 + 7, inv = mod / 2 + 1;
long long f[N], n, fib[N], a[N], b[N], c[N], type, ans;
void fwt(long long *a) {
  for (long long d = 1; d < n; d <<= 1)
    for (long long m = d << 1, i = 0; i < n; i += m)
      for (long long j = 0; j < d; j++) {
        long long x = a[i + j], y = a[i + j + d];
        if (type == 1)
          a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod;
        if (type == 0) a[i + j] = (x + y) % mod;
      }
}
void UFWT(long long *a) {
  for (long long d = 1; d < n; d <<= 1)
    for (long long m = d << 1, i = 0; i < n; i += m)
      for (long long j = 0; j < d; j++) {
        long long x = a[i + j], y = a[i + j + d];
        if (type == 1)
          a[i + j] = 1ll * (x + y) * inv % mo,
                a[i + j + d] = (1ll * (x - y) * inv % mo + mo) % mo;
        if (type == 0) a[i + j] = (x + mo - y) % mo;
      }
}
int main() {
  n = read();
  for (long long i = 1; i <= n; ++i) f[read()]++;
  memcpy(a, f, sizeof f);
  memcpy(b, f, sizeof f);
  memcpy(c, f, sizeof f);
  memset(f, 0, sizeof f);
  n = (1 << 17) - 1;
  fib[1] = 1;
  for (long long i = 2; i <= n; ++i) fib[i] = (fib[i - 2] + fib[i - 1]) % mod;
  for (long long i = 0; i <= n; ++i) {
    long long j = i;
    while (1) {
      f[i] += a[j] * a[i ^ j];
      if (j == 0) break;
      j = (j - 1) & i;
    }
    f[i] %= mod;
  }
  type = 1;
  fwt(b);
  for (long long i = 0; i <= n; ++i) b[i] = b[i] * (b[i]) % mod;
  UFWT(b);
  for (long long i = 0; i <= n; ++i) f[i] = fib[i] * f[i] % mod;
  for (long long i = 0; i <= n; ++i) b[i] = fib[i] * b[i] % mod;
  for (long long i = 0; i <= n; ++i) a[i] = fib[i] * a[i] % mod;
  type = 0;
  fwt(f);
  fwt(a);
  fwt(b);
  for (long long i = 0; i <= n; ++i)
    f[i] = f[i] * (a[i]) % mod, f[i] = f[i] * (b[i]) % mod;
  UFWT(f);
  for (long long i = 1; i < n; i <<= 1) ans = (ans + (f[i])) % mod;
  writeln(ans);
}