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;
template <class T, class V>
ostream &operator<<(ostream &s, pair<T, V> a) {
  s << a.first << ' ' << a.second;
  return s;
}
long long int bigmod(long long int a, long long int p, long long int m) {
  long long int res = 1, x = a;
  while (p) {
    if (p & 1) res = (res * x) % m;
    x = (x * x) % m;
    p >>= 1;
  }
  return res;
}
void XOR(vector<long long int> &a, bool inv = false) {
  int M = a.size();
  for (int len = 2, l2 = 1; len <= M; len <<= 1, l2 <<= 1) {
    for (int i = 0, inc = M / len; i < M; i += len) {
      for (int j = 0, l = 0; j < l2; j++, l += inc) {
        long long int u = a[i + j], v = a[i + j + l2];
        a[i + j] = (u + v >= (1000000007) ? u + v - (1000000007) : u + v);
        a[i + j + l2] = (u - v < 0 ? u - v + (1000000007) : u - v);
      }
    }
  }
  if (inv) {
    long long int m = bigmod(M, (1000000007) - 2, (1000000007));
    for (auto &x : a) x = x * m % (1000000007);
  }
}
void AND(vector<long long int> &a, bool inv = false) {
  int M = a.size();
  for (int len = 2, l2 = 1; len <= M; len <<= 1, l2 <<= 1) {
    for (int i = 0, inc = M / len; i < M; i += len) {
      for (int j = 0, l = 0; j < l2; j++, l += inc) {
        long long int u = a[i + j], v = a[i + j + l2];
        if (inv) {
          a[i + j] = (-u + v < 0 ? v - u + (1000000007) : v - u);
          a[i + j + l2] = u;
        } else {
          a[i + j] = v;
          a[i + j + l2] =
              (u + v >= (1000000007) ? u + v - (1000000007) : u + v);
        }
      }
    }
  }
}
void OR(vector<long long int> &a, bool inv = false) {
  int M = a.size();
  for (int len = 2, l2 = 1; len <= M; len <<= 1, l2 <<= 1) {
    for (int i = 0, inc = M / len; i < M; i += len) {
      for (int j = 0, l = 0; j < l2; j++, l += inc) {
        long long int u = a[i + j], v = a[i + j + l2];
        if (inv) {
          a[i + j] = v;
          a[i + j + l2] = (u - v < 0 ? u - v + (1000000007) : u - v);
        } else {
          a[i + j] = (u + v >= (1000000007) ? u + v - (1000000007) : u + v);
          a[i + j + l2] = u;
        }
      }
    }
  }
}
void (*func[3])(vector<long long int> &, bool) = {&XOR, &OR, &AND};
void multiply(vector<long long int> &a, vector<long long int> &b,
              vector<long long int> &v1, int f) {
  int n = max(a.size(), b.size());
  int M = 1;
  while (M < n) M <<= 1;
  v1.resize(M);
  vector<long long int> v2(M);
  for (int i = 0; i < a.size(); i++) v1[i] = a[i];
  for (int i = 0; i < b.size(); i++) v2[i] = b[i];
  func[f](v1, false);
  func[f](v2, false);
  for (int i = 0; i < M; i++) v1[i] = v1[i] * v2[i] % (1000000007);
  func[f](v1, true);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int qq = 1; qq <= T; qq++) {
    int n;
    cin >> n;
    vector<long long int> f(1 << 17);
    f[0] = 0, f[1] = 1;
    for (int i = 2; i < (1 << 17); i++)
      f[i] = (f[i - 1] + f[i - 2]) % (1000000007);
    vector<long long int> v(1 << 17);
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      v[x]++;
    }
    vector<long long int> v1(1 << 17), v2 = v;
    multiply(v2, v2, v2, 0);
    for (int i = 0; i < v1.size(); i++) {
      for (int j = i;; j = (j - 1) & i) {
        v1[i] += v[j] * v[j ^ i];
        if (!j) break;
      }
      v1[i] %= (1000000007);
    }
    for (int i = 0; i < (1 << 17); i++)
      v1[i] = v1[i] * f[i] % (1000000007), v2[i] = v2[i] * f[i] % (1000000007),
      v[i] = v[i] * f[i] % (1000000007);
    multiply(v1, v2, v1, 2);
    multiply(v, v1, v, 2);
    long long int ans = 0;
    for (int i = 0; i < 17; i++) ans = (ans + v[1 << i]) % (1000000007);
    cout << ans << endl;
  }
}