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.