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;
int add(const int& a, const int& b) {
  int c = a + b;
  if (c >= (int)(1e9 + 7)) c -= (int)(1e9 + 7);
  return c;
}
int sub(const int& a, const int& b) {
  int c = a - b;
  if (c < 0) c += (int)(1e9 + 7);
  return c;
}
int mul(const int& a, const int& b) { return (a * 1ll * b) % (int)(1e9 + 7); }
int ex(int a, int b = (int)(1e9 + 7) - 2) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a), b /= 2;
  }
  return ans;
}
void andFWHT(vector<int>& A, bool iv = 0) {
  int n = A.size();
  for (int s = 1; s < n; s <<= 1) {
    for (int i = 0; i < n; i += 2 * s) {
      for (int j = 0; j < s; ++j) {
        int u = A[i + j], v = A[i + j + s];
        if (!iv) {
          A[i + j] = v;
          A[i + j + s] =
              u + v >= (int)(1e9 + 7) ? u + v - (int)(1e9 + 7) : u + v;
        } else {
          A[i + j] = v < u ? v - u + (int)(1e9 + 7) : v - u;
          A[i + j + s] = u;
        }
      }
    }
  }
}
void xorFWHT(vector<int>& A, bool iv = 0) {
  int n = A.size();
  for (int s = 1; s < n; s <<= 1) {
    for (int i = 0; i < n; i += 2 * s) {
      for (int j = 0; j < s; ++j) {
        int u = A[i + j], v = A[i + j + s];
        A[i + j] = u + v >= (int)(1e9 + 7) ? u + v - (int)(1e9 + 7) : u + v;
        A[i + j + s] = u < v ? u - v + (int)(1e9 + 7) : u - v;
      }
    }
  }
  if (iv) {
    int x = ex(n);
    for (int i = 0; i < n; ++i) A[i] = mul(A[i], x);
  }
}
const int LN = 17;
const int M = 1 << LN;
void XOR(vector<int>& A) {
  int n = 1;
  while (n <= (int)(A).size()) n <<= 1;
  A.resize(n);
  xorFWHT(A);
  for (int i = 0; i < n; ++i) A[i] = mul(A[i], A[i]);
  xorFWHT(A, 1);
}
void AND(vector<int>& A, vector<int>& B, vector<int>& C) {
  int n = 1;
  while (n <= (int)(A).size()) n <<= 1;
  A.resize(n), B.resize(n), C.resize(n);
  andFWHT(A), andFWHT(B), andFWHT(C);
  for (int i = 0; i < n; ++i) A[i] = mul(A[i], mul(B[i], C[i]));
  andFWHT(A, 1);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> b(M, 0);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    b[x]++;
  }
  vector<int> a(M, 0), c = b;
  for (int i = 0; i < M; ++i) {
    int mask = i ^ (M - 1), j = mask;
    while (j >= 0) {
      a[i | j] = add(a[i | j], mul(b[i], b[j]));
      if (!j) break;
      j = (j - 1) & mask;
    }
  }
  XOR(c);
  int x = 0, y = 1, pev;
  for (int i = 2; i < M; ++i) {
    pev = y, y = add(y, x), x = pev;
    a[i] = mul(a[i], y);
    b[i] = mul(b[i], y);
    c[i] = mul(c[i], y);
  }
  a[0] = b[0] = c[0] = 0;
  int ans = 0;
  AND(a, b, c);
  for (int i = 0; i < LN; ++i) ans = add(ans, a[1 << i]);
  cout << ans;
  return 0;
}