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 N = 1 << 17;
const int MOD = 1000 * 1000 * 1000 + 7;
int n, inv2, a[N], fib[N], bits[N], b[18][N], c[18][N], A[N], B[N], C[N];
inline void read(int& x) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
inline void add(int& x, int y) { x = x + y < MOD ? x + y : x + y - MOD; }
inline int he(int x, int y) { return x + y < MOD ? x + y : x + y - MOD; }
int Pow(int x, int y) {
  int t = 1;
  for (; y; y >>= 1, x = 1LL * x * x % MOD)
    if (y & 1) t = 1LL * t * x % MOD;
  return t;
}
int main() {
  int i, j, d, S;
  read(n);
  inv2 = Pow(2, MOD - 2);
  for (i = 1; i <= n; ++i) read(j), ++a[j];
  for (fib[1] = 1, i = 2; i < N; ++i) fib[i] = he(fib[i - 1], fib[i - 2]);
  for (i = 1; i < N; ++i) bits[i] = bits[i >> 1] + (i & 1);
  for (i = 0; i < N; ++i) b[bits[i]][i] = a[i];
  for (i = 0; i < 18; ++i) {
    for (j = 0; j < 17; ++j)
      for (S = 0; S < N; ++S)
        if (1 << j & S) {
          add(b[i][S], b[i][S ^ (1 << j)]);
        }
  }
  for (i = 0; i < 18; ++i) {
    for (j = 0; j <= i; ++j) {
      for (S = 0; S < N; ++S) {
        add(c[i][S], 1LL * b[j][S] * b[i - j][S] % MOD);
      }
    }
  }
  for (i = 0; i < 18; ++i) {
    for (j = 0; j < 17; ++j) {
      for (S = 1; S < N; ++S)
        if (1 << j & S) {
          add(c[i][S], MOD - c[i][S ^ (1 << j)]);
        }
    }
  }
  for (i = 0; i < N; ++i) A[i] = 1LL * c[bits[i]][i] * fib[i] % MOD;
  for (i = 0; i < N; ++i) B[i] = 1LL * a[i] * fib[i] % MOD, C[i] = a[i];
  for (d = 1; d < N; d <<= 1) {
    for (i = 0; i < N; i += (d << 1)) {
      for (j = 0; j < d; ++j) {
        add(A[i + j], A[i + j + d]);
        add(B[i + j], B[i + j + d]);
        int x = C[i + j], y = C[i + j + d];
        C[i + j] = he(x, y);
        C[i + j + d] = he(x, MOD - y);
      }
    }
  }
  for (i = 0; i < N; ++i)
    A[i] = 1LL * A[i] * B[i] % MOD, C[i] = 1LL * C[i] * C[i] % MOD;
  for (d = 1; d < N; d <<= 1) {
    for (i = 0; i < N; i += (d << 1)) {
      for (j = 0; j < d; ++j) {
        add(A[i + j], MOD - A[i + j + d]);
        int x = C[i + j], y = C[i + j + d];
        C[i + j] = 1LL * (x + y) * inv2 % MOD;
        C[i + j + d] = 1LL * (x - y + MOD) * inv2 % MOD;
      }
    }
  }
  for (i = 0; i < N; ++i) C[i] = 1LL * C[i] * fib[i] % MOD;
  for (d = 1; d < N; d <<= 1) {
    for (i = 0; i < N; i += (d << 1)) {
      for (j = 0; j < d; ++j) {
        add(A[i + j], A[i + j + d]);
        add(C[i + j], C[i + j + d]);
      }
    }
  }
  for (i = 0; i < N; ++i) A[i] = 1LL * A[i] * C[i] % MOD;
  for (d = 1; d < N; d <<= 1) {
    for (i = 0; i < N; i += (d << 1)) {
      for (j = 0; j < d; ++j) {
        add(A[i + j], MOD - A[i + j + d]);
      }
    }
  }
  int ans = 0;
  for (i = 0; i < 17; ++i) add(ans, A[1 << i]);
  printf("%d\n", ans);
  return 0;
}