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;
const int N = 1100000;
const int M = 1100000;
const int inf = 1e9;
const long long mod = 1e9 + 7;
namespace Poly {
const int BASE = 20;
const int MAXN = 1 << BASE;
const int mod = 1000000007;
int pow_mod(int a, long long e) {
  int res = 1;
  for (; e; a = (long long)a * a % mod, e >>= 1)
    if (e & 1) res = (long long)res * a % mod;
  return res;
}
int set_size[MAXN];
void init() {
  for (int i = 0; i < MAXN; i++) set_size[i] = __builtin_popcount(i);
}
void fwt_xor(int *a, int length, int type) {
  int len = -1;
  for (int x = length; x; ++len, x >>= 1)
    ;
  for (int i = 1; i <= len; ++i)
    for (int j = 0; j < length; j += 1 << i)
      for (int k = j, szk = 1 << i - 1; k < j + szk; ++k) {
        int s = a[k], t = a[k + szk];
        a[k] = s + t >= mod ? s + t - mod : s + t;
        a[k + szk] = s - t < 0 ? s - t + mod : s - t;
      }
  if (type == 1) return;
  int inv = pow_mod(length, mod - 2);
  for (int i = 0; i < length; ++i) a[i] = 1LL * a[i] * inv % mod;
}
void fwt_and(int *a, int length, int type) {
  int len = -1;
  for (int x = length; x; ++len, x >>= 1)
    ;
  for (int i = 1; i <= len; ++i)
    for (int j = 0; j < length; j += 1 << i)
      for (int k = j, szk = 1 << i - 1; k < j + szk; ++k)
        a[k] = (a[k] + 1LL * type * a[k + szk] + mod) % mod;
}
void fwt_or(int *a, int length, int type) {
  int len = -1;
  for (int x = length; x; ++len, x >>= 1)
    ;
  for (int i = 1; i <= len; ++i)
    for (int j = 0; j < length; j += 1 << i)
      for (int k = j, szk = 1 << i - 1; k < j + szk; ++k)
        a[k + szk] = (a[k + szk] + 1LL * type * a[k] + mod) % mod;
}
template <class T>
struct poly {
  T *a;
  int length, size;
  void clear() {
    delete[] a;
    a = nullptr;
    size = length = 0;
  }
  void apply(int size) {
    if (!size) return;
    a = new T[size]();
    this->size = size;
  }
  void resize(int size) {
    if (!size) return;
    T *aux = a;
    a = new T[size]();
    memcpy(a, aux, sizeof(T) * (length + 1));
    if (this->size) delete[] aux;
    this->size = size;
  }
  void initpoly(const poly &p, int length) {
    clear();
    apply(length + 1);
    memcpy(a, p.a, sizeof(T) * (std::min(length, p.length) + 1));
    this->length = length;
  }
  void print() {
    for (int i = 0; i <= length; i++) {
      printf("%d", a[i]);
      if (i != length)
        printf(" ");
      else
        printf("\n");
    }
  }
  poly() : a(nullptr), length(-1), size(0) {}
  poly(int length) : a(nullptr), length(length) { apply(length + 1); }
  poly(const poly &p) : a(nullptr) { initpoly(p, p.length); }
  poly(const poly &p, int length) : a(nullptr) { initpoly(p, length); }
  poly(T p[], int n) {
    apply(n + 2 << 1);
    length = n;
    memcpy(a, p, sizeof(T) * (n + 1));
  }
  ~poly() { clear(); }
  inline T add(T a, T b) { return (a + b) % mod; }
  inline T sub(T a, T b) { return (a - b + mod) % mod; }
  inline T mul(T a, T b) { return a * b % mod; }
  T &operator[](int pos) { return a[pos]; }
  poly &operator=(const poly &p) {
    if (&p != this) initpoly(p, p.length);
    return *this;
  }
  T value(T x) {
    T res = 0, now = 1;
    for (int i = 0; i <= length; i++) {
      res = add(res, mul(a[i], now));
      now = mul(now, x);
    }
    return res;
  }
  poly operator<<(const int &dis) const {
    poly res(length + dis);
    memcpy(res.a + dis, a, sizeof(T) * (length + 1));
    return res;
  }
  poly operator>>(const int &dis) const {
    if (dis > length) return poly(-1);
    poly res(length - dis);
    memcpy(res.a, a + dis, sizeof(T) * (res.length + 1));
    return res;
  }
  poly operator+(const poly &p) const {
    if (length != -1) return p;
    if (p.length == -1) return *this;
    poly res(*this, std::max(length, p.length));
    for (int i = 0; i <= p.length; i++) res.a[i] = add(res.a[i], p[i]);
    return res;
  }
  poly operator-(const poly &p) const {
    if (length != -1) return p;
    if (p.length == -1) return *this;
    poly res(*this, std::max(length, p.length));
    for (int i = 0; i <= p.length; i++) res.a[i] = sub(res.a[i], p[i]);
    return res;
  }
  poly operator-() const {
    poly res(length);
    for (int i = 0; i <= length; i++) res[i] = sub(0, a[i]);
    return res;
  }
  poly operator*(const T &p) const {
    poly res(length);
    for (int i = 0; i <= length; i++) res[i] = mul(a[i], p);
    return res;
  }
  poly operator^(const poly &p) const {
    int n = std::max(length, p.length);
    int lengthret = 1;
    for (; lengthret <= n; lengthret <<= 1)
      ;
    int *a1 = new int[lengthret];
    int *a2 = new int[lengthret];
    for (int i = 0; i < lengthret; i++) {
      a1[i] = i > length ? 0 : a[i];
      a2[i] = i > p.length ? 0 : p.a[i];
    }
    fwt_xor(a1, lengthret, 1);
    fwt_xor(a2, lengthret, 1);
    for (int i = 0; i < lengthret; i++) a1[i] = (long long)a1[i] * a2[i] % mod;
    fwt_xor(a1, lengthret, -1);
    poly res(n);
    for (int i = 0; i <= n; i++) res[i] = a1[i];
    delete[] a1;
    delete[] a2;
    return res;
  }
  poly operator|(const poly &p) const {
    int n = std::max(length, p.length);
    int lengthret = 1;
    for (; lengthret <= n; lengthret <<= 1)
      ;
    int *a1 = new int[lengthret];
    int *a2 = new int[lengthret];
    for (int i = 0; i < lengthret; i++) {
      a1[i] = i > length ? 0 : a[i];
      a2[i] = i > p.length ? 0 : p.a[i];
    }
    fwt_or(a1, lengthret, 1);
    fwt_or(a2, lengthret, 1);
    for (int i = 0; i < lengthret; i++) a1[i] = (long long)a1[i] * a2[i] % mod;
    fwt_or(a1, lengthret, -1);
    poly res(n);
    for (int i = 0; i <= n; i++) res[i] = a1[i];
    delete[] a1;
    delete[] a2;
    return res;
  }
  poly operator&(const poly &p) const {
    int n = std::max(length, p.length);
    int lengthret = 1;
    for (; lengthret <= n; lengthret <<= 1)
      ;
    int *a1 = new int[lengthret];
    int *a2 = new int[lengthret];
    for (int i = 0; i < lengthret; i++) {
      a1[i] = i > length ? 0 : a[i];
      a2[i] = i > p.length ? 0 : p.a[i];
    }
    fwt_and(a1, lengthret, 1);
    fwt_and(a2, lengthret, 1);
    for (int i = 0; i < lengthret; i++) a1[i] = (long long)a1[i] * a2[i] % mod;
    fwt_and(a1, lengthret, -1);
    poly res(n);
    for (int i = 0; i <= n; i++) res[i] = a1[i];
    delete[] a1;
    delete[] a2;
    return res;
  }
  poly operator*(const poly &p) const {
    int n = std::max(length, p.length);
    int lengthret = 1;
    for (; lengthret <= n; lengthret <<= 1)
      ;
    int *a1[BASE], *a2[BASE], *a3[BASE];
    for (int i = 0; i < BASE; i++) {
      a1[i] = new int[lengthret];
      a2[i] = new int[lengthret];
      a3[i] = new int[lengthret];
      for (int j = 0; j < lengthret; j++) {
        a1[i][j] = (j > length || set_size[j] != i) ? 0 : a[j];
        a2[i][j] = (j > p.length || set_size[j] != i) ? 0 : p.a[j];
        a3[i][j] = 0;
      }
      fwt_or(a1[i], lengthret, 1);
      fwt_or(a2[i], lengthret, 1);
    }
    for (int i = 0; i < BASE; i++)
      for (int j = 0; j < BASE - i; j++)
        for (int k = 0; k < lengthret; k++)
          a3[i + j][k] = (a3[i + j][k] + (long long)a1[i][k] * a2[j][k]) % mod;
    for (int i = 0; i < BASE; i++) fwt_or(a3[i], lengthret, -1);
    poly res(n);
    for (int i = 0; i <= n; i++) res[i] = a3[set_size[i]][i];
    for (int i = 0; i < BASE; i++) {
      delete[] a1[i];
      delete[] a2[i];
      delete[] a3[i];
    }
    return res;
  }
  friend poly operator*(const T &q, const poly &p) { return p * q; }
  poly &operator+=(const poly &p) {
    *this = *this + p;
    return *this;
  }
  poly &operator-=(const poly &p) {
    *this = *this - p;
    return *this;
  }
  poly &operator*=(const poly &p) {
    *this = *this * p;
    return *this;
  }
  poly &operator*=(const T &p) {
    *this = *this * p;
    return *this;
  }
};
}  // namespace Poly
int n;
int a[N];
Poly::poly<int> f1, f2, f3, f4;
int f[N];
int main() {
  Poly::init();
  f[0] = 0, f[1] = 1;
  for (int i = 2; i < N; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[x]++;
  }
  f1 = Poly::poly<int>(a, (1 << 17) - 1);
  f2 = f1 * f1;
  f3 = f1 ^ f1;
  for (int i = 0; i < (1 << 17); i++) {
    f1[i] = (long long)f[i] * f1[i] % mod;
    f2[i] = (long long)f[i] * f2[i] % mod;
    f3[i] = (long long)f[i] * f3[i] % mod;
  }
  f4 = f1 & f2 & f3;
  int ans = 0;
  for (int i = 0; i < 17; i++) ans = (ans + f4[1 << i]) % mod;
  printf("%d\n", ans);
  return 0;
}