Problem: You are given n integers a1, a2, ..., an.

A sequence of integers x1, x2, ..., xk is called a "xor-sequence" if for every 1 ≤ i ≤ k - 1 the number of ones in the binary representation of the number xi <image> xi + 1's is a multiple of 3 and <image> for all 1 ≤ i ≤ k. The symbol <image> is used for the binary exclusive or operation.

How many "xor-sequences" of length k exist? Output the answer modulo 109 + 7.

Note if a = [1, 1] and k = 1 then the answer is 2, because you should consider the ones from a as different.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) — the number of given integers and the length of the "xor-sequences".

The second line contains n integers ai (0 ≤ ai ≤ 1018).

Output

Print the only integer c — the number of "xor-sequences" of length k modulo 109 + 7.

Examples

Input

5 2
15 1 2 4 8


Output

13


Input

5 1
15 1 2 4 8


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void Print() { cout << endl; }
template <typename T1, typename... T>
void Print(const T1 &t1, const T &...t) {
  cout << t1 << " ";
  Print(t...);
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
long long gcd(long long a, long long b) {
  if (b) {
    long long r = a % b;
    a = b, b = r;
  }
  return a;
}
tuple<long long, long long, long long> extend_gcd(long long a, long long b) {
  if (b == 0)
    return make_tuple(a, 1, 0);
  else {
    long long g, nx, ny;
    std::tie(g, nx, ny) = extend_gcd(b, a % b);
    return make_tuple(g, ny, nx - (a / b) * ny);
  }
}
long long fastpow(long long a, long long e, long long mod) {
  if (e == 0) return 1;
  if (e == 1) return a % mod;
  long long t = fastpow(a, e / 2, mod);
  t = t * t % mod;
  if (e & 1)
    return t * a % mod;
  else
    return t % mod;
}
const double PI = 3.14159265358979323846;
const int MOD = (int)1e9 + 7;
template <typename T>
struct Matrix {
  T **e, *d;
  int n, m;
  Matrix() : n(0), m(0), d(nullptr), e(nullptr) {}
  Matrix(int _n, int _m) : n(_n), m(_m) {
    d = new T[n * m];
    e = new T *[n];
    for (int i = 0; i < n; ++i) e[i] = d + m * i;
    memset(d, 0, sizeof(T) * n * m);
  }
  Matrix(const Matrix &rhs) {
    n = rhs.n, m = rhs.m;
    d = new T[n * m];
    e = new T *[n];
    for (int i = 0; i < n; ++i) e[i] = d + m * i;
    memcpy(d, rhs.d, sizeof(T) * n * m);
  }
  Matrix &operator=(Matrix rhs) {
    swap(rhs.n, n);
    swap(rhs.m, m);
    swap(rhs.e, e);
    swap(rhs.d, d);
    return *this;
  }
  Matrix operator*(const Matrix &rhs) const {
    Matrix r(n, rhs.m);
    for (int i = 0; i < n; ++i)
      for (int k = 0; k < m; ++k)
        for (int j = 0; j < rhs.m; ++j)
          r.e[i][j] += e[i][k] * rhs.e[k][j] % MOD;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) r.e[i][j] %= MOD;
    return r;
  }
  ~Matrix() {
    delete[] d;
    delete[] e;
  }
};
const int N = 105;
int n;
long long k;
long long vals[N];
Matrix<long long> matpow(const Matrix<long long> &s, long long e) {
  int n = s.n;
  if (e == 1)
    return s;
  else if (e == 0) {
    Matrix<long long> r(s.n, s.n);
    for (int i = 0; i < n; ++i) r.e[i][i] = 1;
    return r;
  } else {
    auto h = matpow(s, e / 2);
    h = h * h;
    if (e & 1)
      return h * s;
    else
      return h;
  }
}
int cnt(long long a, long long b) {
  long long c = a ^ b;
  int ret = 0;
  for (int i = 0; i < 64; ++i) {
    if (c & (1ll << i)) ++ret;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> vals[i];
  Matrix<long long> m(n, n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (cnt(vals[i], vals[j]) % 3 == 0) m.e[i][j] = 1;
    }
  }
  auto mp = matpow(m, k - 1);
  long long ans = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) ans += mp.e[i][j];
  ans %= MOD;
  Print(ans);
  return 0;
}