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;
template <class A>
ostream &operator<<(ostream &out, const vector<A> &v) {
  for (long long i = 0; i < v.size(); i++) {
    if (i) out << " ";
    out << v[i];
  }
  return out << '\n';
}
const long long mod = 1000000007;
inline long long add(long long a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
inline long long sub(long long a, long long b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
inline long long mul(long long a, long long b) { return (a * 1ll * b) % mod; }
inline long long powmod(long long a, long long b) {
  long long rt = 1;
  while (b > 0) {
    if (b & 1) rt = mul(rt, a);
    a = mul(a, a);
    b >>= 1;
  }
  return rt;
}
inline long long inv(long long a) { return powmod(a, mod - 2); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const long long NN = 101;
class matrix {
 public:
  long long mat[NN][NN];
  long long r, c;
  matrix() {
    for (long long i = 0; i <= NN - 1; i++)
      for (long long j = 0; j <= NN - 1; j++) mat[i][j] = 0;
  }
  void setsize(long long _r, long long _c) { r = _r, c = _c; }
  inline matrix operator*(const matrix &a) {
    assert(c == a.r);
    matrix temp;
    temp.setsize(r, a.c);
    for (long long i = 0; i <= r - 1; i++)
      for (long long j = 0; j <= a.c - 1; j++) {
        for (long long k = 0; k <= a.r - 1; k++) {
          temp.mat[i][j] += (mat[i][k] * a.mat[k][j]) % mod;
          if (temp.mat[i][j] >= mod) temp.mat[i][j] -= mod;
        }
      }
    return temp;
  }
  inline matrix operator+(const matrix &a) {
    assert(r == a.r && c == a.c);
    matrix temp;
    temp.setsize(r, c);
    for (long long i = 0; i <= r - 1; i++)
      for (long long j = 0; j <= c - 1; j++) {
        temp.mat[i][j] = mat[i][j] + a.mat[i][j];
        if (temp.mat[i][j] >= mod) temp.mat[i][j] -= mod;
      }
    return temp;
  }
  inline matrix operator-(const matrix &a) {
    assert(r == a.r && c == a.c);
    matrix temp;
    temp.setsize(r, c);
    for (long long i = 0; i <= r - 1; i++)
      for (long long j = 0; j <= c - 1; j++) {
        temp.mat[i][j] = mat[i][j] - a.mat[i][j];
        if (temp.mat[i][j] < 0) temp.mat[i][j] += mod;
      }
    return temp;
  }
  inline void operator=(const matrix &a) {
    for (long long i = 0; i <= r - 1; i++)
      for (long long j = 0; j <= c - 1; j++) mat[i][j] = a.mat[i][j];
    r = a.r, c = a.c;
  }
  inline void print() {
    for (long long i = 0; i <= r - 1; i++) {
      for (long long j = 0; j <= c - 1; j++) cout << mat[i][j] << " ";
      cout << '\n';
    }
  }
};
matrix pow(matrix a, long long k) {
  assert(a.r == a.c);
  matrix ans;
  for (long long i = 0; i <= a.r - 1; i++) ans.mat[i][i] = 1;
  ans.r = a.r;
  ans.c = a.r;
  while (k) {
    if (k & 1) ans = ans * a;
    a = a * a;
    k >>= 1;
  }
  return ans;
}
const long long N = 101;
long long n, k;
long long a[N];
matrix b;
void solve() {
  cin >> n >> k;
  for (long long i = 0; i < n; i++) cin >> a[i];
  b.setsize(n, n);
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      if ((__builtin_popcountll(a[i] ^ a[j])) % 3 == 0)
        b.mat[i][j] = 1;
      else
        b.mat[i][j] = 0;
    }
  }
  matrix bb = pow(b, k - 1);
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      ans = ans + bb.mat[i][j];
      ans %= mod;
    }
  }
  ans %= mod;
  cout << ans << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL),
      cout << setprecision(14);
  ;
  long long t = 1;
  while (t--) {
    solve();
  }
}