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 $\text{[math]}$ x_{i + 1}'s is a multiple of 3 and $\text{[math]}$ for all 1 ≤ i ≤ k. The symbol $\text{[math]}$ 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.

Input

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¹⁸).

Output

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

Xor-sequences

Examples