设 $M$ 为绝对值不超过 $n$ 的整数集合，即 $M = \{x \in \mathbb{Z} : |x| \le n\}$。 设 $f_k(x)$ 为函数 $f$ 作用于初始值 $x$ 共 $k$ 次的结果，即 $f_0(x) = x$ 且对于任意 $i \ge 1$，有 $f_i(x) = f(f_{i-1}(x))$。 给定整数 $n$ 和 $k$，计算满足以下条件的函数 $f(x)$ 的数量：

1. $f : M \to M$，
2. $\forall x \in M : f_k(x) = -x$，
3. $\forall x \in M : |(|f(x)| - |x|)| \le 2$。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。 每个测试用例包含一对正整数 $n$ 和 $k$ ($n \cdot k \le 10^9$)。 所有测试用例中 $n \cdot k$ 的总和不超过 $4 \cdot 10^9$。

输出格式

对于每个测试用例，在单独的一行中输出答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

7
1 1
2 1
100 1
1 2
2 2
3 2
20 4

样例输出 1

1
1
1
0
2
0
1048576

说明

若 $k = 1$，只有函数 $f(x) = -x$ 满足所有要求。 若 $n = k = 2$，存在两个函数： $(-2, -1, 0, 1, 2) \to (1, 2, 0, -2, -1)$ 以及 $(-2, -1, 0, 1, 2) \to (-1, 2, 0, -2, 1)$。