给定 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