bobo 有一个包含 $n$ 个整数的集合 $\{a_1, a_2, \dots, a_n\}$。他随机选择一个子集 $\{x_1, x_2, \dots, x_m\}$（每个子集被选中的概率相等），并想知道 $[\text{popcount}(x_1 \oplus x_2 \oplus \dots \oplus x_m)]^k$ 的期望值。

注意，$\text{popcount}(x)$ 是 $x$ 二进制表示中 $1$ 的个数，$\oplus$ 表示按位异或运算。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n \le 44, 1 \le k \le 10^9$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{44}$)。

输出格式

如果期望值为 $E$，请输出一个整数，表示 $E \cdot 2^n \pmod{10^9 + 7}$。

样例

样例输入 1

3 2
1 2 3

样例输出 1

12

样例输入 2

2 1000000000
1 2

样例输出 2

140625003