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 <typename T>
inline void read(T& x) {
  int f = 0, c = getchar();
  x = 0;
  while (!isdigit(c)) f |= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
  read(x);
  read(args...);
}
template <typename T>
void write(T x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
void writes(T x) {
  write(x);
  putchar(' ');
}
template <typename T>
void writeln(T x) {
  write(x);
  puts("");
}
template <typename T>
inline bool chkmin(T& x, const T& y) {
  return y < x ? (x = y, true) : false;
}
template <typename T>
inline bool chkmax(T& x, const T& y) {
  return x < y ? (x = y, true) : false;
}
const int maxn = (int)2e5 + 10;
const long long inf = (long long)1e18;
const long long mod = (long long)1e9 + 7;
vector<vector<long long> > iden(int n) {
  vector<vector<long long> > r =
      vector<vector<long long> >(n, vector<long long>(n, 0));
  for (int i = 0; i < n; i++) r[i][i] = 1;
  return r;
}
vector<vector<long long> > mul(vector<vector<long long> > a,
                               vector<vector<long long> > b, int m) {
  vector<vector<long long> > r = vector<vector<long long> >(
      (int)a.size(), vector<long long>((int)b[0].size(), 0));
  for (int i = (0); i < ((int)a.size()); i++)
    for (int j = (0); j < ((int)b[0].size()); j++)
      for (int k = (0); k < ((int)b.size()); k++) {
        r[i][j] += a[i][k] * b[k][j] % m;
        if (r[i][j] >= m) r[i][j] -= m;
      }
  return r;
}
vector<vector<long long> > pw(vector<vector<long long> > a, long long b,
                              int m) {
  vector<vector<long long> > r = iden((int)a.size());
  for (; b; b >>= 1, a = mul(a, a, m))
    if (b & 1) r = mul(r, a, m);
  return r;
}
long long n, k, ans, a[101];
bool check(long long x) {
  int cnt = 0;
  while (x) {
    if (x & 1) cnt++;
    x >>= 1;
  }
  return cnt % 3 == 0;
}
int main() {
  read(n, k);
  for (int i = (0); i < (n); i++) read(a[i]);
  if (k == 1) return writeln(n), 0;
  vector<vector<long long> > d(n, vector<long long>(n, 0));
  for (int i = (0); i < (n); i++)
    for (int j = (i); j < (n); j++) {
      if (check(a[i] ^ a[j])) {
        d[i][j] = d[j][i] = 1;
      }
    }
  vector<vector<long long> > r = pw(d, k - 1, mod);
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) {
      ans = (ans + r[i][j]) % mod;
    }
  writeln(ans);
}