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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/*
 public class _691E {

 }

 */

public class _691E
{
	int mod = (int) 1e9 + 7;

	public void solve() throws FileNotFoundException
	{
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		// actual solution

		int n = inputHelper.readInteger();
		long k = inputHelper.readLong();

		if (k == 1)
		{
			System.out.println(n);
			return;
		}

		long[] a = new long[n];

		for (int i = 0; i < n; i++)
		{
			a[i] = inputHelper.readLong();
		}

		long[][] m = new long[n][n];

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (isValid(a[i], a[j]))
				{
					m[i][j] = 1;
				}
				else
				{
					m[i][j] = 0;
				}
			}
		}

		long[][] ansm = matrix_expo(m, k - 1);

		long ans = 0;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				ans += ansm[i][j];
				ans %= mod;
			}
		}

		System.out.println(ans);
		// end here
	}

	public long[][] matrix_expo(long[][] a, long p)
	{
		if (p == 1)
		{
			return a;
		}

		if ((p & 1) == 0)
		{
			long[][] t = matrix_expo(a, p / 2);
			return matrix_multiply(t, t);
		}
		else
		{
			long[][] t = matrix_expo(a, p / 2);
			t = matrix_multiply(t, t);
			return matrix_multiply(t, a);
		}
	}

	boolean isValid(long a, long b)
	{
		long xor = a ^ b;

		int o = 0;

		while (xor > 0)
		{
			xor = xor & (xor - 1);
			o++;
		}

		return o % 3 == 0;
	}

	public long[][] matrix_multiply(long[][] a, long[][] b)
	{
		int r = a.length;
		int m = a[0].length;
		int c = b[0].length;

		long[][] f = new long[r][c];

		for (int i = 0; i < r; i++)
		{
			for (int j = 0; j < c; j++)
			{
				f[i][j] = 0;
				for (int k = 0; k < m; k++)
				{
					f[i][j] += a[i][k] * b[k][j];
					f[i][j] %= mod;
				}
			}
		}

		return f;
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		(new _691E()).solve();
	}

	class InputHelper
	{
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream)
		{
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					String line = bufferedReader.readLine();
					if (line == null)
					{
						return null;
					}
					tokenizer = new StringTokenizer(line);
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger()
		{
			return Integer.parseInt(read());
		}

		public Long readLong()
		{
			return Long.parseLong(read());
		}
	}
}