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>
template <typename T>
T pow(T value, int64_t power, T result) {
  while (power) {
    if (power & 1) {
      result *= value;
    }
    value *= value;
    power >>= 1;
  }
  return result;
}
template <typename T>
T pow(T value, int64_t power) {
  return pow(value, power, T(1));
}
template <uint32_t MOD>
struct ModInt {
  uint32_t v;
  ModInt() : v{0} {}
  ModInt(int64_t v) : v{normS(v % MOD + MOD)} {}
  explicit operator bool() const { return v != 0; }
  static uint32_t normS(uint32_t x) { return (x < MOD) ? x : x - MOD; }
  static ModInt make(uint32_t x) {
    ModInt m;
    m.v = x;
    return m;
  }
  static ModInt inv(const ModInt &x) { return pow(ModInt(x), MOD - 2); }
  ModInt operator+(const ModInt &r) const { return make(normS(v + r.v)); }
  ModInt operator-(const ModInt &r) const { return make(normS(v + MOD - r.v)); }
  ModInt operator*(const ModInt &r) const {
    return make(int64_t(v) * r.v % MOD);
  }
  ModInt operator/(const ModInt &r) const { return *this * inv(r); }
  ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
  ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
  ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
  ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
};
constexpr int MOD = 1e9 + 7;
using int_m = ModInt<MOD>;
const int_m inv = 742744451;
constexpr int M = 20;
constexpr int m = 17;
constexpr int N = (1 << 17);
std::array<int_m, N> a, b, e, f, c[M], d[M];
template <bool inverse>
void or_transform(std::array<int_m, N> &P) {
  for (std::size_t len = 1; len < N; len <<= 1) {
    for (std::size_t i = 0; i < N; i += 2 * len) {
      for (std::size_t j = 0; j < len; ++j) {
        if constexpr (!inverse) {
          P[i + len + j] += P[i + j];
        } else {
          P[i + len + j] -= P[i + j];
        }
      }
    }
  }
}
void hadamard(std::array<int_m, N> &P) {
  for (std::size_t len = 1; len < N; len <<= 1) {
    for (std::size_t i = 0; i < N; i += 2 * len) {
      for (std::size_t j = 0; j < len; ++j) {
        int_m u = P[i + j];
        int_m v = P[i + len + j];
        P[i + j] = u + v;
        P[i + len + j] = u - v;
      }
    }
  }
}
template <bool inverse>
void and_transform(std::array<int_m, N> &P) {
  for (std::size_t len = 1; len < N; len <<= 1) {
    for (std::size_t i = 0; i < N; i += 2 * len) {
      for (std::size_t j = 0; j < len; ++j) {
        if constexpr (!inverse) {
          P[i + j] += P[i + len + j];
        } else {
          P[i + j] -= P[i + len + j];
        }
      }
    }
  }
}
std::array<int, 1 << 17> bit;
void solve(std::istream &in, std::ostream &out) {
  int n;
  in >> n;
  f[1] = 1;
  for (std::size_t i = 2; i < N; ++i) {
    f[i] = f[i - 1] + f[i - 2];
  }
  for (std::size_t i = 0, val; i < n; ++i) {
    in >> val;
    a[val] += 1;
    b[val] += 1;
    c[__builtin_popcount(val)][val] += 1;
  }
  for (std::size_t cnt = 0; cnt <= m; ++cnt) {
    or_transform<false>(c[cnt]);
  }
  for (std::size_t x = 0; x <= m; ++x) {
    for (std::size_t y = 0; x + y <= m; ++y) {
      for (std::size_t i = 0; i < N; ++i) {
        d[x + y][i] += c[x][i] * c[y][i];
      }
    }
  }
  for (std::size_t cnt = 0; cnt <= m; ++cnt) {
    or_transform<true>(d[cnt]);
  }
  hadamard(b);
  for (std::size_t i = 0; i < N; ++i) {
    b[i] *= b[i];
  }
  hadamard(b);
  for (std::size_t i = 0; i < N; ++i) {
    b[i] *= inv;
  }
  for (std::size_t i = 0; i < N; ++i) {
    a[i] *= f[i];
    b[i] *= f[i];
    e[i] = d[__builtin_popcount(i)][i] * f[i];
  }
  and_transform<false>(a);
  and_transform<false>(b);
  and_transform<false>(e);
  for (std::size_t i = 0; i < N; ++i) {
    a[i] *= b[i] * e[i];
  }
  and_transform<true>(a);
  int_m res = 0;
  for (int i = 0; i < m; ++i) {
    res += a[1 << i];
  }
  out << res.v << '\n';
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cerr.tie(nullptr);
  solve(std::cin, std::cout);
  return 0;
}