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>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
template <unsigned MOD>
struct ModInt {
  static const unsigned static_MOD = MOD;
  unsigned x;
  void undef() { x = (unsigned)-1; }
  bool isnan() const { return x == (unsigned)-1; }
  inline int geti() const { return (int)x; }
  ModInt() { x = 0; }
  ModInt(const ModInt &y) { x = y.x; }
  ModInt(int y) {
    if (y < 0 || (int)MOD <= y) y %= (int)MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned y) {
    if (MOD <= y)
      x = y % MOD;
    else
      x = y;
  }
  ModInt(long long y) {
    if (y < 0 || MOD <= y) y %= MOD;
    if (y < 0) y += MOD;
    x = y;
  }
  ModInt(unsigned long long y) {
    if (MOD <= y)
      x = y % MOD;
    else
      x = y;
  }
  ModInt &operator+=(const ModInt y) {
    if ((x += y.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt y) {
    if ((x -= y.x) & (1u << 31)) x += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt y) {
    x = (unsigned long long)x * y.x % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt y) {
    x = (unsigned long long)x * y.inv().x % MOD;
    return *this;
  }
  ModInt operator-() const { return (x ? MOD - x : 0); }
  ModInt inv() const {
    unsigned a = MOD, b = x;
    int u = 0, v = 1;
    while (b) {
      int t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) u += MOD;
    return ModInt(u);
  }
  ModInt pow(long long y) const {
    ModInt b = *this, r = 1;
    if (y < 0) {
      b = b.inv();
      y = -y;
    }
    for (; y; y >>= 1) {
      if (y & 1) r *= b;
      b *= b;
    }
    return r;
  }
  friend ModInt operator+(ModInt x, const ModInt y) { return x += y; }
  friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; }
  friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; }
  friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); }
  friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; }
  friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; }
  friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; }
};
const long long MOD = 1000000007;
template <class T>
void fwht(T *x, const int n) {
  static T *y = NULL;
  static int y_len = 0;
  if (y_len < n) {
    if (y) delete[] y;
    y_len = n;
    y = new T[y_len];
  }
  int nn = n, s = 1, eo = 0;
  for (; nn > 1;) {
    const int m = nn >> 1;
    for (int p = 0; p < m; p++) {
      for (int q = 0; q < s; q++) {
        const T a = x[q + s * p];
        const T b = x[q + s * (p + m)];
        y[q + s * (p + p)] = a + b;
        y[q + s * (p + p + 1)] = a - b;
      }
    }
    nn = m;
    s += s;
    eo ^= 1;
    swap(x, y);
  }
  if (eo) {
    for (int q = 0; q < s; q++) y[q] = x[q];
    swap(x, y);
  }
}
int N;
const int SIZE = 1 << 17;
const ModInt<MOD> invSize = ModInt<MOD>(1) / SIZE;
ModInt<MOD> Pxor[SIZE];
ModInt<MOD> Sa[SIZE], Sor[SIZE];
ModInt<MOD> G[SIZE];
ModInt<MOD> fib[SIZE];
void Zsuper(ModInt<MOD> s[]) {
  for (int t = 0, t_len = (17); t < t_len; ++t)
    for (int i = 0, i_len = (SIZE); i < i_len; ++i)
      if (~i >> t & 1) s[i | (1 << t)] += s[i];
}
void Zsub(ModInt<MOD> s[]) {
  for (int t = 0, t_len = (17); t < t_len; ++t)
    for (int i = 0, i_len = (SIZE); i < i_len; ++i)
      if (~i >> t & 1) s[i] += s[i | (1 << t)];
}
void MAIN() {
  scanf("%d", &N);
  for (int i = 0, i_len = (N); i < i_len; ++i) {
    int x;
    scanf("%d", &x);
    Sa[x] += 1;
    Pxor[x] += 1;
  }
  fib[1] = 1;
  for (int i = 0, i_len = (SIZE - 2); i < i_len; ++i)
    fib[i + 2] = fib[i] + fib[i + 1];
  for (int i = 0, i_len = (SIZE); i < i_len; ++i) {
    for (int sub = i;; sub = i & (sub - 1)) {
      Sor[i] += Pxor[sub] * Pxor[i - sub];
      if (sub == 0) break;
    }
  }
  fwht(Pxor, SIZE);
  for (int i = 0, i_len = (SIZE); i < i_len; ++i) Pxor[i] *= Pxor[i];
  fwht(Pxor, SIZE);
  for (int i = 0, i_len = (SIZE); i < i_len; ++i) Pxor[i] *= invSize;
  for (int i = 0, i_len = (SIZE); i < i_len; ++i) {
    Sa[i] = fib[i] * Sa[i];
    Sor[i] = fib[i] * Sor[i];
    Pxor[i] = fib[i] * Pxor[i];
  }
  Zsub(Sa);
  Zsub(Sor);
  Zsub(Pxor);
  for (int i = 0, i_len = (SIZE); i < i_len; ++i)
    G[i] = Sa[i] * Sor[i] * Pxor[i];
  for (int t = 0, t_len = (17); t < t_len; ++t)
    for (int i = SIZE; i--;)
      if (~i >> t & 1) G[i] -= G[i | (1 << t)];
  ModInt<MOD> ans = 0;
  for (int t = 0, t_len = (17); t < t_len; ++t) ans += G[1 << t];
  printf("%d\n", ans.geti());
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}