题目描述
梅子，青涩的梅子。
小 $\mu$ 发现了一个 $n$ 行 $m$ 列的迷宫，第 $x$ 行第 $y$ 列的坐标为 $(x,y)$，初始所有格子为未探索状态，我们将进行 $10^{1233^{1337}}$ 次找宝藏。
每次找宝藏时从 $(1,1)$ 出发，设当前格子为 $(x,y)$：若当前格子为未探索状态，将其变成探索状态，然后向 $(x+1,y)$ 移动；若当前格子为探索状态，将其变成未探索状态，然后向 $(x,y+1)$ 移动。如果走出迷宫则这次找宝藏结束。
现在想知道在 $10^{1233^{1337}}$ 次找宝藏后，本质不同的迷宫状态个数。定义两个迷宫相同当且仅当对于所有格子是否探索的状态都一样。
由于答案很大，答案对 $998244353$ 取模。本题多测。
输入格式
第一行一个非负数 $T$，表示数据组数。
接下来 $T$ 行输入两个正整数 $n,m$，表示迷宫的行和列。
输出格式
输出 $T$ 行，每行一个正整数，表示本质不同的迷宫个数，答案对 $998244353$ 取模。
样例一
input
4
1 1
2 2
3 3
2 4output
2
4
16
16样例二
input
5
154 154
1233 1337
114514 1919810
8181891 12331337
1000000000000000000 1000000000000000000output
726449253
545706585
950465985
63834604
152973038样例三
见下发文件。
限制与约定
对于所有数据，保证 $T\leq 2 \times10^5,1\leq n,m\leq 10^{18}$。
本题有九个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。
| 子任务编号 | 子任务分数 | 特殊限制 |
|---|---|---|
| $1$ | $1$ | $T=0$ |
| $2$ | $4$ | $T=4,n,m\leq 2$ |
| $3$ | $15$ | $T=100,n,m\leq 10$ |
| $4$ | $20$ | $n=m$ |
| $5$ | $10$ | $n=1$ |
| $6$ | $10$ | $T \leq 10,n,m \leq 1000$ |
| $7$ | $10$ | $T \leq 10,n,m \leq 10^6$ |
| $8$ | $20$ | $n,m \le 10^9$ |
| $9$ | $10$ | 无特殊限制 |
时间限制： $1\texttt{s}$
空间限制： $1024\texttt{MB}$