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 B = 17;
const int MX = 1 << B;
const int mod = 1e9 + 7;
const int rev2 = (mod + 1) / 2;
int add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
int mult(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) {
  a -= b;
  return a < 0 ? a += mod : a;
}
vector<int> adamant(vector<int> x, bool rev) {
  int n = x.size();
  for (int i = 0; i < B; ++i) {
    for (int j = 0; j < n; ++j)
      if ((j >> i & 1) == 0) {
        int j1 = j ^ (1 << i);
        int a = x[j], b = x[j1];
        x[j] = add(a, b);
        x[j1] = sub(a, b);
      }
  }
  if (rev)
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < B; ++j) x[i] = mult(x[i], rev2);
    }
  return x;
}
vector<int> upsets(vector<int> v) {
  for (int j = 0; j < B; ++j)
    for (int i = 0; i < MX; ++i)
      if (!(i >> j & 1)) v[i] = add(v[i], v[i ^ (1 << j)]);
  return v;
}
vector<int> rev(vector<int> v) {
  for (int j = 0; j < B; ++j)
    for (int i = 0; i < MX; ++i)
      if (!(i >> j & 1)) v[i] = sub(v[i], v[i ^ (1 << j)]);
  return v;
}
int main() {
  ios::sync_with_stdio(false);
  int sz;
  cin >> sz;
  vector<int> cnt(MX);
  for (int i = 0; i < sz; ++i) {
    int x;
    cin >> x;
    ++cnt[x];
  }
  vector<int> fib(MX);
  fib[1] = 1;
  for (int i = 2; i < MX; ++i) fib[i] = add(fib[i - 1], fib[i - 2]);
  vector<int> cntab(MX);
  for (int i = 0; i < MX; ++i) {
    for (int j = i; j > 0; --j, j &= i)
      cntab[i] = add(cntab[i], mult(cnt[j], cnt[i ^ j]));
    cntab[i] = add(cntab[i], mult(cnt[i], cnt[0]));
  }
  vector<int> cntc = cnt;
  auto cntde = adamant(cnt, false);
  for (int i = 0; i < MX; ++i) cntde[i] = mult(cntde[i], cntde[i]);
  cntde = adamant(cntde, true);
  for (int i = 0; i < MX; ++i) {
    cntab[i] = mult(cntab[i], fib[i]);
    cntc[i] = mult(cntc[i], fib[i]);
    cntde[i] = mult(cntde[i], fib[i]);
  }
  cntab = upsets(cntab);
  cntc = upsets(cntc);
  cntde = upsets(cntde);
  for (int i = 0; i < MX; ++i)
    cntab[i] = mult(cntab[i], mult(cntc[i], cntde[i]));
  cntab = rev(cntab);
  int ans = 0;
  for (int i = 0; i < B; ++i) ans = add(ans, cntab[1 << i]);
  cout << ans << endl;
}