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;
using ll = long long;
using ld = long double;
using vi = vector<long long>;
using vii = vector<pair<long long, long long> >;
const long long INFI = 1e9 + 228;
const ll INFL = 1e18 + 228;
const ld INFLD = 1e18 + 228;
const ld PI = acos(-1);
const long long MAXN = 2e5 + 228;
vii DD = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct matrix {
  long long n, m;
  vector<vector<long long> > zn;
  matrix(long long rn, long long rm) {
    n = rn;
    m = rm;
    for (long long i = 0; i < n; ++i) {
      zn.push_back(vector<long long>());
      for (long long j = 0; j < m; ++j) {
        zn[i].push_back(0);
      }
    }
  }
};
matrix zero(long long n) {
  matrix now = matrix(n, n);
  for (long long i = 0; i < n; ++i) {
    now.zn[i][i] = 1;
  }
  return now;
}
long long add_mod(long long a, long long b, long long mod) {
  if (a + b >= mod) return a + b - mod;
  return a + b;
}
matrix pr(matrix a, matrix b, long long mod = -1) {
  matrix c = matrix(a.n, b.m);
  for (long long i = 0; i < a.n; ++i) {
    for (long long j = 0; j < b.m; ++j) {
      for (long long k = 0; k < a.m; ++k) {
        if (mod != -1)
          c.zn[i][j] = add_mod(c.zn[i][j], a.zn[i][k] * b.zn[k][j] % mod, mod);
        else
          c.zn[i][j] += a.zn[i][k] * b.zn[k][j];
      }
    }
  }
  return c;
}
void write(matrix a) {
  for (long long i = 0; i < a.n; ++i) {
    for (long long j = 0; j < a.m; ++j) {
      cerr << a.zn[i][j] << ' ';
    }
    cerr << endl;
  }
}
struct segtree {
  segtree *l = nullptr, *r = nullptr;
  long long lb, rb;
  long long sum = 0, add = 0;
  segtree(long long L, long long R) {
    lb = L;
    rb = R;
    if (lb + 1 < rb) {
      long long m = (lb + rb) / 2;
      l = new segtree(lb, m);
      r = new segtree(m, rb);
    }
  }
  void push() {
    sum += (rb - lb) * add;
    if (lb + 1 < rb) {
      l->add += add;
      r->add += add;
    }
    add = 0;
  }
  void upd(long long L, long long R, long long delta) {
    if (R <= lb || rb <= L) return;
    if (L <= lb && rb <= R) {
      add += delta;
      return;
    }
    l->upd(L, R, delta);
    r->upd(L, R, delta);
    sum = l->sum + r->sum + ((rb - lb) / 2) * (l->add + r->add);
  }
  long long get(long long L, long long R) {
    if (R <= lb || rb <= L) return 0;
    if (L <= lb && rb <= R) return sum + add;
    push();
    return l->get(L, R) + r->get(L, R);
  }
};
matrix binpow(matrix a, long long n, long long mod) {
  if (n == 0) return zero(a.n);
  matrix ans = binpow(a, n / 2, mod);
  ans = pr(ans, ans, mod);
  if (n % 2 == 1) return pr(ans, a, mod);
  return ans;
}
bool check(long long x) {
  long long kol = 0;
  while (x > 0) {
    kol += x % 2;
    x /= 2;
  }
  return kol % 3 == 0;
}
void run() {
  long long n, k;
  cin >> n >> k;
  vector<long long> mass;
  for (long long i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    mass.push_back(x);
  }
  long long mod = 1e9 + 7;
  matrix per = matrix(n, n);
  matrix start = matrix(n, n);
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < n; ++j) {
      if (check(mass[i] ^ mass[j])) {
        per.zn[i][j] = 1;
      }
    }
  }
  for (long long i = 0; i < n; ++i) start.zn[i][i] = 1;
  matrix ans = pr(start, binpow(per, k - 1, mod), mod);
  long long sum = 0;
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < n; ++j) {
      sum = (sum + ans.zn[i][j]) % mod;
    }
  }
  cout << sum << endl;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) run();
  return 0;
}