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>
const int N = 1 << 17, P = 1e9 + 7;
int n, Fib[N], s[N], a[18][N], b[18][N], c[N], d[N], e[N], f[N], Ans;
inline void re(int &x) { x += x >> 31 & P; }
void fwtor(int *f, int o) {
  for (int l = 1; l < 131072; l <<= 1)
    for (int i = 0; i < 131072; i += l << 1)
      for (int j = i; j < i + l; j++)
        if (!o)
          re(f[j + l] += f[j] - P);
        else
          re(f[j + l] -= f[j]);
}
void fwtxor(int *f, int o) {
  int x, y;
  for (int l = 1; l < 131072; l <<= 1)
    for (int i = 0; i < 131072; i += l << 1)
      for (int j = i; j < i + l; j++) {
        x = f[j];
        y = f[j + l];
        re(f[j] = x + y - P);
        re(f[j + l] = x - y);
        if (o) {
          f[j] = (long long)f[j] * 500000004 % P;
          f[j + l] = (long long)f[j + l] * 500000004 % P;
        }
      }
}
void fwtand(int *f, int o) {
  for (int l = 1; l < 131072; l <<= 1)
    for (int i = 0; i < 131072; i += l << 1)
      for (int j = i; j < i + l; j++)
        if (!o)
          re(f[j] += f[j + l] - P);
        else
          re(f[j] -= f[j + l]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    ++s[x];
  }
  Fib[1] = 1;
  for (int i = 2; i < 131072; i++) Fib[i] = (Fib[i - 1] + Fib[i - 2]) % P;
  for (int i = 0; i < 131072; i++) {
    a[__builtin_popcount(i)][i] = s[i];
    d[i] = (long long)s[i] * Fib[i] % P;
    e[i] = s[i];
  }
  for (int i = 0; i <= 17; i++) fwtor(a[i], 0);
  for (int i = 0; i <= 17; i++)
    for (int j = 0; j <= 17; j++)
      if (i + j <= 17)
        for (int k = 0; k < 131072; k++)
          b[i + j][k] = (b[i + j][k] + (long long)a[i][k] * a[j][k]) % P;
  for (int i = 0; i <= 17; i++) fwtor(b[i], 1);
  for (int i = 0; i < 131072; i++)
    c[i] = (long long)b[__builtin_popcount(i)][i] * Fib[i] % P;
  fwtxor(e, 0);
  for (int i = 0; i < 131072; i++) e[i] = (long long)e[i] * e[i] % P;
  fwtxor(e, 1);
  for (int i = 0; i < 131072; i++) e[i] = (long long)e[i] * Fib[i] % P;
  fwtand(c, 0);
  fwtand(d, 0);
  fwtand(e, 0);
  for (int i = 0; i < 131072; i++) f[i] = (long long)c[i] * d[i] % P * e[i] % P;
  fwtand(f, 1);
  for (int i = 0; i < 17; i++) Ans = (Ans + f[1 << i]) % P;
  printf("%d", Ans);
  return 0;
}