CF691E.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 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.

给你 $ n $ 个整数 $ a_1,,a_2,,\dots,,a_n $。

一个整数序列 $ x_1,,x_2,,\dots,,x_k $ 被称为“异或序列”（xor-sequence），当且仅当对每个 $ 1\le i\le k-1 $，数 $ x_i \oplus x_{i+1} $ 的二进制表示中 1 的个数是 3 的倍数，且对所有 $ 1\le i\le k $，均有 $ x_i \in {a_1,,a_2,,\dots,,a_n} $。其中符号 $ \oplus $ 表示二进制按位异或运算。

长度为 $ k $ 的“异或序列”共有多少个？请输出答案对 $ 10^9 + 7 $ 取模的结果。

注意：若 $ a = [1,,1] $ 且 $ k = 1 $，则答案为 2，因为需将 $ a $ 中的两个 1 视为不同的元素。

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 a__i (0 ≤ a__i ≤ 1018).

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100$，$1 \leq k \leq 10^{18}$）—— 分别表示给定整数的个数以及“异或序列”（xor-sequence）的长度。

第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^{18}$）。

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

输出唯一的整数 $c$ —— 长度为 $k$ 的“异或序列”（xor-sequences）的个数，对 $10^9 + 7$ 取模。