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>
int pos = 1 << 17;
char buf[1 << 17];
inline char nextch() {
  if (pos == 1 << 17) fread(buf, 1 << 17, 1, stdin), pos = 0;
  return buf[pos++];
}
inline int read() {
  char ch;
  while (!isdigit(ch = nextch()))
    ;
  int x = ch - '0';
  while (isdigit(ch = nextch())) x = 10 * x + ch - '0';
  return x;
}
const int N = 1 << 17;
int ab[132000], de[132000], fr[132000], fib[132000];
inline int lgput(int a, int n) {
  int r = 1;
  while (n) {
    if (n % 2) r = 1LL * r * a % 1000000007;
    n /= 2;
    a = 1LL * a * a % 1000000007;
  }
  return r;
}
void fwht(int *data, int dim) {
  for (int len = 1; 2 * len <= dim; len <<= 1) {
    for (int i = 0; i < dim; i += 2 * len) {
      for (int j = 0; j < len; j++) {
        int a = data[i + j];
        int b = data[i + j + len];
        data[i + j] = a + b;
        if (data[i + j] >= 1000000007) data[i + j] -= 1000000007;
        data[i + j + len] = a - b;
        if (data[i + j + len] < 0) data[i + j + len] += 1000000007;
      }
    }
  }
}
void to_transform(int dim, int *data) {
  int len, i, j, u, v;
  for (len = 1; 2 * len <= dim; len <<= 1) {
    for (i = 0; i < dim; i += 2 * len) {
      for (j = 0; j < len; j++) {
        u = data[i + j];
        v = data[i + len + j];
        data[i + j] = v;
        data[i + len + j] = u + v;
        if (data[i + len + j] >= 1000000007) data[i + len + j] -= 1000000007;
      }
    }
  }
}
void inv_transform(int dim, int *data) {
  int len, i, j, u, v;
  for (len = 1; 2 * len <= dim; len <<= 1) {
    for (i = 0; i < dim; i += 2 * len) {
      for (j = 0; j < len; j++) {
        u = data[i + j];
        v = data[i + len + j];
        data[i + j] = v - u;
        data[i + len + j] = u;
        if (data[i + j] < 0) data[i + j] += 1000000007;
      }
    }
  }
}
int main() {
  int n = read();
  for (int i = 0; i < n; i++) fr[read()]++;
  for (int i = 0; i < N; i++) {
    for (int j = i; j; j = (j - 1) & i)
      ab[i] = (ab[i] + 1LL * fr[j] * fr[i ^ j]) % 1000000007;
    ab[i] = (ab[i] + 1LL * fr[0] * fr[i]) % 1000000007;
  }
  for (int i = 0; i < N; i++) de[i] = fr[i];
  fwht(de, N);
  for (int i = 0; i < N; i++) de[i] = 1LL * de[i] * de[i] % 1000000007;
  fwht(de, N);
  int inv = lgput(N, 1000000007 - 2);
  for (int i = 0; i < N; i++) de[i] = 1LL * de[i] * inv % 1000000007;
  fib[1] = 1;
  for (int i = 2; i < N; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= 1000000007) fib[i] -= 1000000007;
  }
  for (int i = 0; i < N; i++) ab[i] = 1LL * ab[i] * fib[i] % 1000000007;
  to_transform(N, ab);
  for (int i = 0; i < N; i++) fr[i] = 1LL * fr[i] * fib[i] % 1000000007;
  to_transform(N, fr);
  for (int i = 0; i < N; i++) ab[i] = 1LL * ab[i] * fr[i] % 1000000007;
  inv_transform(N, ab);
  to_transform(N, ab);
  for (int i = 0; i < N; i++) de[i] = 1LL * de[i] * fib[i] % 1000000007;
  to_transform(N, de);
  for (int i = 0; i < N; i++) ab[i] = 1LL * ab[i] * de[i] % 1000000007;
  inv_transform(N, ab);
  int ans = 0;
  for (int i = 1; i < N; i++)
    if (i - (i & (-i)) == 0) ans = (ans + ab[i]) % 1000000007;
  printf("%d\n", ans);
  return 0;
}