← 返回题目列表

Codeforces · 1557/C

C. 莫阿门和异或

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

Moamen 和 Ezzat 正在玩游戏。他们创建一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$,其中每个元素都小于 $$$2^k$$$。

如果 $$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \o​​plus \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]$$$。