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 JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class XorSequences {

	static class Solver {

		int N, eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee = 1;
		long a[], MOD = 1_000_000_007, K;
		long[] m[];

		long[][] mat_mult(long[][] A, long[] B[]) {
			long res[][] = new long[N][N];
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					for (int k = 0; k < N; k++) {
						res[i][j] += A[i][k] * B[k][j];
						if (res[i][j] >= MOD)
							res[i][j] %= MOD;
					}
			return res;
		}

		void solve(FastScanner s, PrintWriter out) {
			N = s.nextInt();
			K = s.nextLong();
			a = s.nextLongArray(N);
			m = new long[N][N];
			for (int i = 0; i < N; i++)
				for (int j = i; j < N; j++)
					if (Long.bitCount(a[i] ^ a[j]) % 3 == 0)
						m[i][j] = m[j][i] = 1;

			long[][] atharva_is_a_doo_doo_head_and_i_think_he_should_quit_juggling = mat_pow(m, K - 1);
			long tot = 0;
			for (long[] a : atharva_is_a_doo_doo_head_and_i_think_he_should_quit_juggling)
				for (long b : a)
					tot = (tot + b) % MOD;
			out.printf("%d%n", tot);

		}

		long[][] mat_pow(long[][] A, long eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee) {
			if (eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee == 0)
				return ident(N);
			long[][] _two = mat_mult(A, A);
			if ((eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee & 1) == 0)
				return mat_pow(_two, eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee >> eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee);
			else {
				return mat_mult(A,
						mat_pow(_two, eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee >> eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee));
			}

		}

	}

	public static void main(String[] args) {
		FastScanner s = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		Solver solver = new Solver();
		solver.solve(s, out);

		out.close();
	}

	private static long[][] ident(Integer N) {
		long[][] Return_Matrix = new long[N][N];
		for (Integer I = 1; I <= N; I++)
			Return_Matrix[I - 1][I - 1] = 1;
		return Return_Matrix;
	}

	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		// Jacob Garbage

		public int[] nextIntArray(int N) {
			int[] ret = new int[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextInt();
			return ret;
		}

		public long[] nextLongArray(int N) {
			long[] ret = new long[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextLong();
			return ret;
		}

		public int[][] next2DIntArray(int N, int M) {
			int[][] ret = new int[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextIntArray(M);
			return ret;
		}

		public double[] nextDoubleArray(int N) {
			double[] ret = new double[N];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDouble();
			return ret;
		}

		public double[][] next2DDoubleArray(int N, int M) {
			double[][] ret = new double[N][];
			for (int i = 0; i < N; i++)
				ret[i] = this.nextDoubleArray(M);
			return ret;
		}

	}

}