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>
template <typename T>
void scan(T &x) {
  x = 0;
  bool _ = 0;
  T c = getchar();
  _ = c == 45;
  c = _ ? getchar() : c;
  while (c < 48 || c > 57) c = getchar();
  for (; c < 48 || c > 57; c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) x = (x << 3) + (x << 1) + (c & 15);
  x = _ ? -x : x;
}
template <typename T>
void printn(T n) {
  bool _ = 0;
  _ = n < 0;
  n = _ ? -n : n;
  char snum[65];
  int i = 0;
  do {
    snum[i++] = n % 10 + 48;
    n /= 10;
  } while (n);
  --i;
  if (_) putchar(45);
  while (i >= 0) putchar(snum[i--]);
}
template <typename First, typename... Ints>
void scan(First &arg, Ints &...rest) {
  scan(arg);
  scan(rest...);
}
template <typename T>
void print(T n) {
  printn(n);
  putchar(10);
}
template <typename First, typename... Ints>
void print(First arg, Ints... rest) {
  printn(arg);
  putchar(32);
  print(rest...);
}
using namespace std;
using T = long long;
constexpr T mod = 1e9 + 7;
struct matrix {
  int n, m;
  vector<vector<T>> a;
  matrix(int _n = 0, int _m = 0) {
    n = _n, m = _m;
    a.resize(n);
    for (int i = 0; i < n; i++) a[i].resize(m);
  }
};
matrix mul(matrix ma, matrix mb) {
  matrix c(ma.n, mb.m);
  for (int i = 0; i < ma.n; i++) {
    for (int j = 0; j < mb.m; j++) {
      T t = 0;
      for (int k = 0; k < ma.m; k++) t = (t + ma.a[i][k] * mb.a[k][j]) % mod;
      c.a[i][j] = t;
    }
  }
  return c;
}
matrix fpow(matrix m, T exp) {
  if (exp == 1) return m;
  matrix ret = fpow(m, exp / 2);
  ret = mul(ret, ret);
  if (exp & 1) ret = mul(ret, m);
  return ret;
}
T in[101];
int main() {
  int n;
  T k;
  scan(n, k);
  if (k == 1) {
    return print(n), 0;
  }
  for (int i = 0; i < n; i++) {
    scan(in[i]);
  }
  matrix a(n, n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      a.a[i][j] = (__builtin_popcountll(in[i] ^ in[j]) % 3 == 0);
    }
  }
  a = fpow(a, k - 1);
  T res = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      res += a.a[i][j];
      res %= mod;
    }
  }
  print(res);
  return 0;
}