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 read() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ans = (ans << 1) + (ans << 3) + c - '0';
    c = getchar();
  }
  return ans * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x / 10) write(x / 10);
  putchar((char)(x % 10) + '0');
}
template <typename T>
inline T Abs(T a) {
  return a > 0 ? a : -a;
};
template <typename T, typename TT>
inline T Min(T a, TT b) {
  return a > b ? b : a;
}
template <typename T, typename TT>
inline T Max(T a, TT b) {
  return a > b ? a : b;
}
const long long NN = 1e6 + 5, N = 4e5 + 5, M = 20, mod = 1e9 + 7;
long long n, m, s[NN], c[N], f1[N], f2[N], f5[N], fib[N];
long long AND[2][2] = {{1, 1}, {0, 1}}, IAND[2][2] = {{1, mod - 1}, {0, 1}};
long long OR[2][2] = {{1, 0}, {1, 1}}, IOR[2][2] = {{1, 0}, {mod - 1, 1}};
long long XOR[2][2] = {{1, 1}, {1, mod - 1}},
          IXOR[2][2] = {{500000004, 500000004}, {500000004, mod - 500000004}};
struct Poly {
  long long a[M];
  void operator+=(const Poly &b) {
    for (long long i = 0; i <= 17; ++i) a[i] = (a[i] + b.a[i]) % mod;
  }
  void operator-=(const Poly &b) {
    for (long long i = 0; i <= 17; ++i) a[i] = (a[i] - b.a[i] + mod) % mod;
  }
  Poly operator*(const Poly &b) const {
    Poly res;
    memset(res.a, 0, sizeof(long long) * (18));
    for (long long i = 0; i <= 17; ++i)
      for (long long j = 0; i + j <= 17; ++j)
        res.a[i + j] = (res.a[i + j] + a[i] * b.a[j] % mod) % mod;
    return res;
  }
} f3[N], f4[N];
inline long long q_pow(long long a, long long b);
inline void DWT(Poly *a, long long n);
inline void IDWT(Poly *a, long long n);
inline void failed_system_test(Poly *a, Poly *b, long long n);
inline long long init(long long n);
inline void mul(long long *a, long long *b, long long c[2][2],
                long long ic[2][2], long long n);
inline void fast_will_tle(long long *a, long long c[2][2], long long n);
signed main() {
  n = read();
  fib[1] = 1;
  for (long long i = 1; i <= n; ++i) s[i] = read(), m = Max(m, s[i]);
  m = init(m);
  for (long long i = 1; i < m; ++i) {
    c[i] = c[i >> 1] + (i & 1);
    if (i != 1) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  }
  for (long long i = 1; i <= n; ++i) {
    f1[s[i]]++, f2[s[i]]++;
    f3[s[i]].a[c[s[i]]]++;
    f4[s[i]].a[c[s[i]]]++;
  }
  failed_system_test(f3, f4, m);
  for (long long i = 0; i < m; ++i) f5[i] = f3[i].a[c[i]] * fib[i];
  mul(f1, f2, XOR, IXOR, m);
  for (long long i = 0; i < m; ++i) f1[i] = f1[i] * fib[i];
  memset(f2, 0, sizeof(long long) * (m));
  for (long long i = 1; i <= n; ++i) f2[s[i]]++;
  for (long long i = 0; i < m; ++i) f2[i] = f2[i] * fib[i];
  mul(f1, f2, AND, IAND, m);
  mul(f1, f5, AND, IAND, m);
  long long ans = 0;
  for (long long i = 1; i < m; i <<= 1) ans = (ans + f1[i]) % mod;
  printf("%lld\n", ans);
  return 0;
}
inline long long q_pow(long long a, long long b) {
  long long c = 1;
  while (b) {
    if (b & 1) c = a * c % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return c;
}
inline void DWT(Poly *a, long long n) {
  for (long long l = 2; l <= n; l <<= 1) {
    long long len = l >> 1;
    for (long long i = 0; i < n; i += l)
      for (long long k = 0; k < len; ++k) a[len | i | k] += a[i | k];
  }
}
inline void IDWT(Poly *a, long long n) {
  for (long long l = 2; l <= n; l <<= 1) {
    long long len = l >> 1;
    for (long long i = 0; i < n; i += l)
      for (long long k = 0; k < len; ++k) a[len | i | k] -= a[i | k];
  }
}
inline void failed_system_test(Poly *a, Poly *b, long long n) {
  DWT(a, n);
  DWT(b, n);
  for (long long i = 0; i < n; ++i) a[i] = a[i] * b[i];
  IDWT(a, n);
}
inline long long init(long long n) {
  long long res = 1;
  for (; res <= n; res <<= 1)
    ;
  return res;
}
inline void mul(long long *a, long long *b, long long c[2][2],
                long long ic[2][2], long long n) {
  fast_will_tle(a, c, n);
  fast_will_tle(b, c, n);
  for (long long i = 0; i < n; ++i) a[i] = a[i] * b[i] % mod;
  fast_will_tle(a, ic, n);
}
inline void fast_will_tle(long long *a, long long c[2][2], long long n) {
  for (long long l = 2; l <= n; l <<= 1) {
    long long len = l >> 1;
    for (long long i = 0; i < n; i += l)
      for (long long k = i; k < i + len; ++k) {
        long long tmp = a[k];
        a[k] = (c[0][0] * tmp + c[0][1] * a[k + len]) % mod;
        a[k + len] = (c[1][0] * tmp + c[1][1] * a[k + len]) % mod;
      }
  }
}