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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long b, long long e, long long m) {
  b %= m;
  long long ans = 1;
  for (; e; b = b * b % m, e /= 2)
    if (e & 1) ans = ans * b % m;
  return ans;
}
const long long M = 1e9 + 7;
inline long long sum(long long a, long long b) {
  return a + b >= M ? a + b - M : a + b;
}
inline long long sub(long long a, long long b) {
  return a - b < 0 ? a - b + M : a - b;
}
inline long long mult(long long a, long long b) { return a * (long long)b % M; }
const long long N = (1 << 17);
void FST(vector<long long>& a, bool inv) {
  for (long long n = ((long long)a.size()), step = 1; step < n; step *= 2) {
    for (long long i = 0; i < n; i += 2 * step)
      for (long long j = i; j < (i + step); ++j) {
        long long &u = a[j], &v = a[j + step];
        tie(u, v) = pair<long long, long long>(u + v, u - v);
      }
  }
  if (inv)
    for (auto& x : a) x /= ((long long)a.size());
}
vector<long long> conv(vector<long long> a, vector<long long> b) {
  FST(a, 0);
  FST(b, 0);
  for (long long i = 0; i < (((long long)a.size())); ++i) a[i] *= b[i];
  FST(a, 1);
  return a;
}
void FST2(vector<long long>& a, bool inv) {
  for (long long n = ((long long)a.size()), step = 1; step < n; step *= 2) {
    for (long long i = 0; i < n; i += 2 * step)
      for (long long j = i; j < (i + step); ++j) {
        long long &u = a[j], &v = a[j + step];
        tie(u, v) = inv ? pair<long long, long long>(sub(v, u), u)
                        : pair<long long, long long>(v, sum(u, v));
      }
  }
}
vector<long long> conv2(vector<long long> a, vector<long long> b) {
  FST2(a, 0);
  FST2(b, 0);
  for (long long i = 0; i < (((long long)a.size())); ++i)
    a[i] = mult(a[i], b[i]);
  FST2(a, 1);
  return a;
}
long long cnt[N];
long long cnt1[N];
long long cnt3[N];
long long fib[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n;
  cin >> n;
  fib[0] = 0;
  fib[1] = 1;
  for (long long i = 2; i < (N); ++i) fib[i] = sum(fib[i - 1], fib[i - 2]);
  for (long long i = 0; i < n; i++) {
    long long x;
    cin >> x;
    cnt[x]++;
  }
  for (long long m = 1; m < N; m++) {
    long long inv = (N - 1) & (~m);
    for (long long s = inv; s; s = (s - 1) & inv) {
      cnt1[m | s] = sum(cnt1[m | s], mult(cnt[m], cnt[s]));
    }
    cnt1[m] = sum(cnt1[m], mult(cnt[m], 2ll * cnt[0] % M));
  }
  vector<long long> vec;
  for (long long i = 0; i < N; i++) vec.push_back(cnt[i]);
  vec = conv(vec, vec);
  vector<long long> v1, v2, v3;
  for (long long i = 0; i < (N); ++i) {
    cnt3[i] = vec[i] % M;
    if (i) {
      v1.push_back(1ll * cnt1[i] % M * fib[i] % M);
      v2.push_back(1ll * cnt[i] % M * fib[i] % M);
      v3.push_back(1ll * cnt3[i] % M * fib[i] % M);
    } else
      v1.push_back(0), v2.push_back(0), v3.push_back(0);
  }
  v1 = conv2(conv2(v1, v2), v3);
  long long p = 1;
  long long res = 0;
  while (p < N) {
    res = sum(res, v1[p]);
    p = p * 2;
  }
  cout << mod(res, M) << "\n";
}