CF1557C.Moamen and XOR

Moamen and Ezzat are playing a game. They create an array $a$ of $n$ non-negative integers where every element is less than $2^k$.

Moamen wins if $a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$.

Here $\&$ denotes the bitwise AND operation, and $\oplus$ denotes the bitwise XOR operation.

Please calculate the number of winning for Moamen arrays $a$.

As the result may be very large, print the value modulo $1\,000\,000\,007$ ($10^9 + 7$).

莫阿门和埃扎特正在玩一个游戏。他们创建一个包含 $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$，则莫阿门获胜。

此处 $\&$ 表示按位与运算，$\oplus$ 表示按位异或运算。

请计算莫阿门获胜的数组 $a$ 的个数。

由于结果可能非常大，请输出其对 $1\,000\,000\,007$（即 $10^9 + 7$）取模的值。

The first line contains a single integer $t$ ($1 \le t \le 5$)— the number of test cases.

Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n\le 2\cdot 10^5$, $0 \le k \le 2\cdot 10^5$).

第一行包含一个整数 $t$（$1 \le t \le 5$）——测试用例的数量。

每个测试用例由一行组成，包含两个整数 $n$ 和 $k$（$1 \le n\le 2\cdot 10^5$，$0 \le k \le 2\cdot 10^5$）。

For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo $1\,000\,000\,007$ ($10^9 + 7$).

对于每个测试用例，输出一个整数——Moamen 获胜的不同数组的个数。

结果对 $1\,000\,000\,007$（即 $10^9 + 7$）取模。

In the first example, $n = 3$, $k = 1$. As a result, all the possible arrays are $[0,0,0]$, $[0,0,1]$, $[0,1,0]$, $[1,0,0]$, $[1,1,0]$, $[0,1,1]$, $[1,0,1]$, and $[1,1,1]$.

Moamen wins in only $5$ of them: $[0,0,0]$, $[1,1,0]$, $[0,1,1]$, $[1,0,1]$, and $[1,1,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]$。