Moamen 和 Ezzat 正在玩游戏。他们创建一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$,其中每个元素都小于 $$$2^k$$$。
如果 $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$$$ 则穆阿门获胜。
这里$$$\&$$$表示按位AND运算,$$$\oplus$$$表示按位XOR运算。
请计算Moamen阵列$$$a$$$的获胜数量。
由于结果可能非常大,因此打印模 $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$) 的值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n\le 2\cdot 10^5$$$, $$$0 \le k \le 2\cdot 10^5$$$)。
输出
对于每个测试用例,打印一个值 - Moamen 获胜的不同数组的数量。
打印对 $$$1\,000\,000\,007$$$ 取模的结果 ($$$10^9 + 7$$$)。
示例
输入 #1
3 3 1 2 1 4 0
输出 #1
5 2 1
注意
在第一个示例中,$$$n = 3$$$,$$$k = 1$$$。因此,所有可能的数组为 $$$[0,0,0]$$$、$$$[0,0,1]$$$、$$$[0,1,0]$$$、$$$[1,0,0]$$$、$$$[1,1,0]$$$、$$$[0,1,1]$$$、$$$[1,0,1]$$$ 和$$$[1,1,1]$$$。
Moamen 仅在其中 $$$5$$$ 中获胜:$$$[0,0,0]$$$、$$$[1,1,0]$$$、$$$[0,1,1]$$$、$$$[1,0,1]$$$ 和 $$$[1,1,1]$$$。