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 nth_bit(int64_t num, int n) { return (num >> n) & 1; }
int pop_count(int bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}
const int64_t MOD = 1e9 + 7;
void add(int64_t& a, int64_t b) { a = (a + b) % MOD; }
void mul(int64_t& a, int64_t b) { a = a * b % MOD; }
struct XORconv {
  vector<int64_t> res;
  template <typename T>
  void fwt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
      for (int j = 0; j < n; j++) {
        if ((j & i) == 0) {
          T x = f[j], y = f[j | i];
          f[j] = x + y, f[j | i] = x - y;
        }
      }
    }
  }
  template <typename T>
  void ifwt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
      for (int j = 0; j < n; j++) {
        if ((j & i) == 0) {
          T x = f[j], y = f[j | i];
          f[j] = (x + y) / 2, f[j | i] = (x - y) / 2;
        }
      }
    }
  }
  XORconv(vector<int64_t> A, vector<int64_t> B) {
    int N = A.size();
    fwt(A);
    fwt(B);
    res.resize(N);
    for (int i = 0; i < N; i++) res[i] = A[i] * B[i];
    ifwt(res);
  }
};
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) scanf("%d", &A[i]);
  const int M = 17;
  vector<int64_t> num(1 << M), F(1 << M);
  for (int a : A) num[a]++;
  F[1] = 1;
  for (int i = 2; i < (1 << M); i++) F[i] = (F[i - 1] + F[i - 2]) % MOD;
  vector<int64_t> res[3];
  res[0].resize(1 << M);
  for (int b = 0; b < (1 << M); b++)
    for (int b1 = b; b1 >= 0; b1 = (b1 - 1) & b) {
      add(res[0][b], num[b1] * num[b - b1]);
      if (b1 == 0) break;
    }
  res[1] = num;
  XORconv xorc(num, num);
  res[2] = xorc.res;
  for (int k = 0; k < 3; k++) {
    auto& r = res[k];
    for (int i = 0; i < (1 << M); i++) {
      r[i] %= MOD;
      mul(r[i], F[i]);
    }
    for (int i = 0; i < M; i++)
      for (int b = 0; b < (1 << M); b++)
        if (nth_bit(b, i)) add(r[b - (1 << i)], r[b]);
  }
  int64_t ans = 0;
  for (int b = 1; b < (1 << M); b++) {
    int cnt = pop_count(b);
    int64_t r = res[0][b] * res[1][b] % MOD * res[2][b] % MOD;
    mul(r, cnt);
    if (cnt % 2 == 0) r = MOD - r;
    add(ans, r);
  }
  cout << ans << endl;
  return 0;
}