A10552 | Xor-sequences

You are given $n$ integers $a_{1},a_{2},...,a_{n}$ .

A sequence of integers $x_{1},x_{2},...,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^{9}+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^{18}$ ) — the number of given integers and the length of the "xor-sequences".

The second line contains $n$ integers $a_{i}$ ( $0<=a_{i}<=10^{18}$ ).

Print the only integer $c$ — the number of "xor-sequences" of length $k$ modulo $10^{9}+7$ .