← 返回题目列表

Codeforces · 691/E

E. 异或序列

中文机器翻译题面 查看原题

给定 n 个整数 a1, a2, ..., an。

整数 x1, x2, ..., xk 的序列称为“异或序列”,如果对于每个 1 ≤ i ≤ k - 1,数字 xi $$\times$$ xi + 1 的二进制表示形式中 1 的数量是 3 的倍数,并且 $$x_i \in \{a_1, a_2, \ldots, a_n\}$$ 对于所有1≤i≤k。符号$$\times$$用于二进制异或运算。

存在多少个长度为 k 的“异或序列”?输出对 109 + 7 取模的答案。

请注意,如果 a = [1, 1] 且 k = 1,则答案为 2,因为您应该将 a 中的值视为不同的。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) — 给定整数的数量和“异或序列”的长度。

第二行包含 n 个整数 ai (0 ≤ ai ≤ 1018)。

输出

打印唯一的整数 c — 长度为 k 模 109 + 7 的“异或序列”的数量。

示例

输入 #1

5 2
15 1 2 4 8

输出 #1

13

输入 #2

5 1
15 1 2 4 8

输出 #2

5