题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。

我们称一个长度为 $k$ 的序列 $b_1,b_2,\dots,b_k$ 是合法序列，当且仅当对任意满足 $1 \le i < k$ 的位置，都有：

$$\operatorname{popcount}(b_i \oplus b_{i+1}) \equiv 0 \pmod{3}$$

其中：

• $\oplus$ 表示按位异或；
• $\operatorname{popcount}(x)$ 表示整数 $x$ 的二进制表示中 $1$ 的个数。

序列中的每一项 $b_i$ 必须从给定的 $n$ 个数中选择，即对于每个 $i$，都有：

$$b_i \in \{a_1,a_2,\dots,a_n\}$$

注意：

• 每个位置都可以独立选择；
• 同一个数值可以被重复选择多次；
• 即使若干个 $a_i$ 的值相同，它们仍然视为不同的可选位置，因此会对方案数产生贡献。

请你求出合法序列的总数。由于答案可能很大，你只需要输出它对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

• $1 \le n \le 100$
• $1 \le k \le 10^{18}$
• $0 \le a_i \le 10^{18}$

输出格式

输出一个整数，表示合法序列的总数对 $10^9+7$ 取模后的结果。

5 2
15 1 2 4 8

13

5 1
15 1 2 4 8

5

Hint

样例解释： 样例 2 中，长度为 1 的序列不需要检查相邻条件，因此直接可以从 5 个位置中任选 1 个，答案为 5。