数表（二）

Problem Description

你得到了一张 $2$ 行的表格，其中第一行有 $n$ 列，第二行有 $n+1$ 列，第一行的第一列和第二行第一列对齐，如图示： 现在需要在这一共 $2n+1$ 个格子中都填入一个整数，需要满足：

• 1、填的整数在 $[0,2^k-1]$ 之间。
• 2、同一行不能有相同的数，同一列不能有相同的数。
• 3、所有 $2n+1$ 个数的异或和恰好是 $0$. 现在Cuking想问你，有多少种不同的填数方案，由于答案可能很大，你需要输出答案在模 $998\ 244\ 353$下的结果。

Input

第一行一个整数 $T(1\leq T\leq 30)$ 表示测试用例数量。 对每个测试用例，输入两个整数 $n,k$，$1\leq n\leq 10^6,1\leq k\leq 10^9$，和题目中的 $n,k$ 对应。

Output

对每组格式用例，输出一行一个整数表示答案。

Sample Input

2
1 2
114 514

Sample Output

9
410645142

Hint

$n=1,k=2$ 的 $9$ 种情况如下：

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）