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 T SQR(T x) {
  return x * x;
}
template <typename T>
inline void UPDATE_MIN(T &x, T y) {
  if (y < x) {
    x = y;
  }
}
template <typename T>
inline void UPDATE_MAX(T &x, T y) {
  if (x < y) {
    x = y;
  }
}
template <typename T>
inline int ARGMAX(T cont) {
  return max_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int ARGMIN(T cont) {
  return min_element(cont.begin(), cont.end()) - cont.begin();
}
template <typename T>
inline int hamming(T x) {
  return __builtin_popcountll((long long)x);
}
int hamming(int x) { return __builtin_popcount(x); }
int hamming(long x) { return __builtin_popcountl(x); }
int hamming(long long x) { return __builtin_popcountll(x); }
vector<string> split(const string &s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s;
  s << "[";
  for (__typeof(n - 1) i = (0), __tmpvar__end89 = (n - 1); i < __tmpvar__end89;
       i++)
    s << arr[i] << ",";
  s << arr[n - 1] << "]";
  return s.str();
}
template <class T>
inline string TOSTR(const T &x) {
  stringstream ss;
  ss << x;
  return ss.str();
}
inline void PR(void) {}
inline void PR(int x) { printf("%d", x); }
inline void PR(long long x) { printf("%lld", x); }
inline void PR(size_t x) { printf("%llu", (unsigned long long)x); }
inline void PR(const char *s) { printf("%s", s); }
inline void PR(double f) { printf("%.10f", f); }
inline void PR(long double f) { printf("%.10f", (double)f); }
template <typename T>
inline void PR(vector<T> &vec) {
  auto sz = vec.size();
  for (auto x : vec) {
    PR(x);
    (--sz) ? putc(0x20, stdout) : 0;
  }
}
template <typename T>
inline void PRS(T x) {
  PR(x);
  putc(0x20, stdout);
}
template <typename T>
inline void PRN(T x) {
  PR(x);
  putc(0x0a, stdout);
}
void PRN(void) { putc(0x0a, stdout); }
struct pairhash {
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};
const int MOD = 1000 * 1000 * 1000 + 7;
const double PI = 3.1415926535897932384626433832795l;
template <typename T>
inline T gcd(T a, T b) {
  return a ? gcd(b % a, a) : b;
}
inline void addto(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void subto(int &a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
inline int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
  return a;
}
inline void multo(int &a, int b) { a = (long long)a * b % MOD; }
inline int mul(int a, int b) { return (long long)a * b % MOD; }
inline int mulmod(int a, int b, int mod) { return (long long)a * b % mod; }
inline int powmod(int a, int e, int mod) {
  int x;
  for (x = 1; e > 0; e >>= 1) {
    if (e & 1) x = mulmod(x, a, mod);
    a = mulmod(a, a, mod);
  }
  return x;
}
inline int invmod_prime(int a, int mod) { return powmod(a, mod - 2, mod); }
inline long long invmod_LL(long long p) {
  long long q = p;
  for (long long a = p * p; a != 1; a *= a) q *= a;
  return q;
}
long long N, K;
long long arr[101] = {};
int M[200][100][100];
vector<int> Mfree;
int mlast = 1;
int mget() {
  if (Mfree.size()) {
    int res = Mfree.back();
    Mfree.pop_back();
    return res;
  }
  int res = mlast++;
  assert(res < 200);
  return res;
}
int matmul(int ia, int ib, bool fa = false, bool fb = false) {
  static const long long MOD2 = MOD * 1ll * MOD;
  int res = mget();
  for (__typeof(N) i = (0), __tmpvar__end233 = (N); i < __tmpvar__end233; i++) {
    int *rowres = M[res][i];
    int *rowa = M[ia][i];
    for (__typeof(N) j = (0), __tmpvar__end236 = (N); j < __tmpvar__end236;
         j++) {
      long long res = 0;
      for (__typeof(N) k = (0), __tmpvar__end238 = (N); k < __tmpvar__end238;
           k++) {
        res += rowa[k] * 1ll * M[ib][k][j];
        if (res > MOD2) res -= MOD2;
      }
      rowres[j] = res % MOD;
    }
  }
  if (fa) Mfree.push_back(ia);
  if (fb && (ia != ib || !fa)) Mfree.push_back(ib);
  return res;
}
int matpow(int ia, long long p) {
  int ires = mget();
  for (__typeof(N) i = (0), __tmpvar__end251 = (N); i < __tmpvar__end251; i++)
    for (__typeof(N) j = (0), __tmpvar__end251 = (N); j < __tmpvar__end251; j++)
      M[ires][i][j] = (i == j);
  int icur = ia;
  while (p > 0) {
    if (p & 1) ires = matmul(ires, icur, 1);
    p >>= 1;
    icur = matmul(icur, icur, icur != ia);
  }
  return ires;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf(
      "%lld"
      "%lld",
      &N, &K);
  if (K == 1) {
    printf("%d\n", (int)N);
    exit(0);
  };
  for (__typeof(N) i = (0), __tmpvar__end265 = (N); i < __tmpvar__end265; i++) {
    scanf("%lld", &arr[i]);
  }
  1;
  int imat = 0;
  for (__typeof(N) i = (0), __tmpvar__end268 = (N); i < __tmpvar__end268; i++) {
    for (__typeof(N) j = (0), __tmpvar__end269 = (N); j < __tmpvar__end269;
         j++) {
      int hw = hamming(arr[i] ^ arr[j]);
      if (hw % 3 == 0) {
        M[imat][i][j] = 1;
        1;
      }
    }
  }
  int ires = matpow(imat, K - 1);
  int ans = 0;
  for (__typeof(N) i = (0), __tmpvar__end279 = (N); i < __tmpvar__end279; i++) {
    for (__typeof(N) j = (0), __tmpvar__end280 = (N); j < __tmpvar__end280;
         j++) {
      addto(ans, M[ires][i][j]);
      if (M[ires][i][j]) {
        1;
      }
    }
  }
  PRN(ans);
  1;
  return 0;
}