该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

异或OR同或 1

时间限制： 1s

空间限制：256MB

BackGround

有天 $TannicAcid$ 在上数字逻辑电路的课程，课中提到了 异或 $($XOR$)$ 和一个运算符 同或 $($XNOR$)$，于是 $TannicAcid$ 马上意识到可以对这个运算符 同或 出一道题。但是在此之前，我们先重新回顾一下关于 异或 的一些性质。

Description

对于一个长度为 $n$ 的非负整数序列, 如果有某个连续子序列的异或和为 $0$ , 则 $TannicAcid$ 不喜欢这个序列，否则喜欢

现在 $TannicAcid$ 给出两个整数 $n$ 和 $m$ ，请你告诉他，由 $0$ ~ $2^m-1$ 组成的所有长度为 $n$ 的序列中，有多少个 $TannicAcid$ 会喜欢的序列

Input Format

第一行包含一个正整数 $T$ ，表示有 $T$ 组数据

第 $2$ ~ $T+1$行每行包含两个正整数 $n$ , $m$

Output Format

对于每个测试用例，输出一个整数，表示 $TannicAcid$ 会喜欢的序列的数量，结果对 $1e9+7$ 取模

Input Example

3
3 2
4 3
5 4

Output Example

6
840
360360

Data Range

• $1\leq T \leq 100$

• $1\leq n , m \leq 2*10^4$