You are given n integers a₁,a₂,...,a_n.

A sequence of integers x₁,x₂,...,x_k is called a "xor-sequence" if for every 1≤i≤k-1 the number of ones in the binary representation of the number x_i x_i+1's is a multiple of 3 and for all 1≤i≤k. The symbol is used for the binary exclusive or operation.

How many "xor-sequences" of length k exist? Output the answer modulo 10⁹+7.

Note if a=[1,1] and k=1 then the answer is 2, because you should consider the ones from a as different.

The first line contains two integers n and k (1≤n≤100, 1≤k≤10¹⁸) − the number of given integers and the length of the "xor-sequences".

The second line contains n integers a_i (0≤a_i≤10¹⁸).

Print the only integer c − the number of "xor-sequences" of length k modulo 10⁹+7.