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 mod = 1e9 + 7;
const int N = 1e6 + 5;
const int LOGN = 17;
const int NN = (1 << LOGN);
int cnt[NN], a[NN], b[NN], c[NN], s[N];
int f[NN];
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = ((long long)ans * a) % mod;
    a = ((long long)a * a) % mod;
    b >>= 1;
  }
  return ans;
}
void or_transform(int *from, int *to) {
  if (to - from == 1) return;
  int *mid = from + (to - from) / 2;
  or_transform(from, mid);
  or_transform(mid, to);
  for (int i = 0; i < mid - from; i++) {
    mid[i] += from[i];
    if (mid[i] >= mod) mid[i] -= mod;
  }
}
void or_inverse(int *from, int *to) {
  if (to - from == 1) return;
  int *mid = from + (to - from) / 2;
  or_inverse(from, mid);
  or_inverse(mid, to);
  for (int i = 0; i < mid - from; i++) {
    mid[i] += mod - from[i];
    if (mid[i] >= mod) mid[i] -= mod;
  }
}
void xor_transform(int *from, int *to) {
  if (to - from == 1) return;
  int *mid = from + (to - from) / 2;
  xor_transform(from, mid);
  xor_transform(mid, to);
  for (int i = 0; i < mid - from; i++) {
    int a = from[i];
    int b = mid[i];
    from[i] = a + b;
    mid[i] = a - b + mod;
    if (from[i] >= mod) from[i] -= mod;
    if (mid[i] >= mod) mid[i] -= mod;
  }
}
void xor_inverse(int *from, int *to) {
  xor_transform(from, to);
  int tot = to - from;
  long long iv = pwr(tot, mod - 2);
  for (int i = 0; i <= tot - 1; i++) {
    from[i] = (from[i] * iv) % mod;
  }
}
void and_transform(int *from, int *to) {
  reverse(from, to);
  or_transform(from, to);
  reverse(from, to);
}
void and_inverse(int *from, int *to) {
  reverse(from, to);
  or_inverse(from, to);
  reverse(from, to);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    cnt[s[i]]++;
    c[s[i]]++;
    b[s[i]]++;
  }
  f[0] = 0, f[1] = 1;
  for (int i = 2; i <= NN - 1; i++) {
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] >= mod) f[i] -= mod;
  }
  xor_transform(c, c + NN);
  for (int i = 0; i <= NN - 1; i++) {
    c[i] = ((long long)c[i] * c[i]) % mod;
  }
  xor_inverse(c, c + NN);
  for (int mask = 0; mask <= NN - 1; mask++) {
    int mmask = mask;
    a[mask] = ((long long)cnt[0] * cnt[mask]) % mod;
    while (mmask > 0) {
      a[mask] += ((long long)cnt[mmask] * cnt[(mask ^ mmask)]) % mod;
      if (a[mask] >= mod) a[mask] -= mod;
      mmask = (mmask - 1) & mask;
    }
  }
  for (int i = 0; i <= NN - 1; i++) {
    a[i] = ((long long)a[i] * f[i]) % mod;
    b[i] = ((long long)b[i] * f[i]) % mod;
    c[i] = ((long long)c[i] * f[i]) % mod;
  }
  and_transform(a, a + NN);
  and_transform(b, b + NN);
  and_transform(c, c + NN);
  for (int i = 0; i <= NN - 1; i++) {
    a[i] = ((long long)a[i] * b[i]) % mod;
    a[i] = ((long long)a[i] * c[i]) % mod;
  }
  and_inverse(a, a + NN);
  int ans = 0;
  for (int i = 0; i <= LOGN - 1; i++) {
    ans += a[(1 << i)];
    if (ans >= mod) ans -= mod;
  }
  cout << ans;
  return 0;
}