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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
const int MAXN = (1 << 17);
const long long MOD = 1000000007LL;
inline long long pw(long long x, long long k) {
  long long res = 1;
  for (long long bs = x; k; k >>= 1, bs = mul(bs, bs)) {
    if (k & 1) res = mul(res, bs);
  }
  return res;
}
inline long long Inv(long long x) { return pw(x, MOD - 2); }
inline void modit(long long& x) {
  if (x < 0) x += MOD;
  if (x >= MOD) x -= MOD;
}
inline void fwt_and(long long x[MAXN], bool inv = 0) {
  for (int d = 1; d < (1 << 17); d <<= 1) {
    int d2 = d << 1;
    for (int s = 0; s < (1 << 17); s += d2) {
      for (int i = s, j = s + d; i < s + d; i++, j++) {
        long long ta = x[i], tb = x[j];
        if (!inv) {
          x[i] = ta + tb;
          x[j] = tb;
        } else {
          x[i] = ta - tb;
          x[j] = tb;
        }
        modit(x[i]);
        modit(x[j]);
      }
    }
  }
}
inline void fwt_xor(long long x[MAXN], bool inv = 0) {
  for (int d = 1; d < (1 << 17); d <<= 1) {
    int d2 = d << 1;
    for (int s = 0; s < (1 << 17); s += d2) {
      for (int i = s, j = s + d; i < s + d; i++, j++) {
        long long ta = x[i], tb = x[j];
        x[i] = ta + tb;
        x[j] = ta - tb;
        modit(x[i]);
        modit(x[j]);
      }
    }
  }
  if (inv)
    for (int i = 0; i < (1 << 17); i++) {
      x[i] *= Inv((1 << 17));
      x[i] %= MOD;
    }
}
int fib[(1 << 17)];
void build() {
  fib[1] = 1;
  for (int i = 2; i < (1 << 17); i++) fib[i] = add(fib[i - 1], fib[i - 2]);
}
int n;
long long s[(1 << 17)], a[(1 << 17)], b[(1 << 17)];
void init() {
  n = getint();
  for (int i = 0; i < n; i++) {
    s[getint()]++;
  }
  for (int i = 0; i < (1 << 17); i++) {
    for (int j = i; j; j = (j - 1) & i) a[i] = add(a[i], mul(s[j], s[i ^ j]));
    a[i] = add(a[i], mul(s[0], s[i]));
    a[i] = mul(fib[i], a[i]);
  }
  for (int i = 0; i < (1 << 17); i++) b[i] = s[i];
  fwt_xor(b);
  for (int i = 0; i < (1 << 17); i++) b[i] = mul(b[i], b[i]);
  fwt_xor(b, 1);
  for (int i = 0; i < (1 << 17); i++) {
    b[i] = mul(fib[i], b[i]);
    s[i] = mul(fib[i], s[i]);
  }
}
void solve() {
  fwt_and(s);
  fwt_and(a);
  fwt_and(b);
  for (int i = 0; i < (1 << 17); i++) s[i] = mul(mul(s[i], a[i]), b[i]);
  fwt_and(s, 1);
  int ans = 0;
  for (int i = 0; i < 17; i++) ans = add(ans, s[(1 << i)]);
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}