The Game Before the Gate

时空限制

$\text{1s} \qquad \text{512MB}$

题目背景

你和 $\text{Albedo}$ 携手参加魔女会的试炼，来到了一个棋盘之上

题目描述

这里有一个 $n \times m$ 的棋盘，$\text{King}$ 和 $\text{Queen}$ 会在棋盘上放置 $n + m$ 枚 $\text{Soldier}$

在每一行左边和每一列上面（不在棋盘内）共有 $n + m$ 个 $\text{Castle}$，每一个 $\text{Castle}$ 可以沿行/列直走吃掉恰好一枚 $\text{Soldier}$

此处的 $\text{Castle}$ 只能走一步，可以越过棋子

$F$ 表示吃掉所有棋子的方案数，$W = F^{k}$ 表示难度系数，$\text{Castle}$ 之间的行动顺序不同算同一个方案

求所有 $F \neq 0$ 的棋子放置情况的 $W$ 之和，对 $998244353$ 取模后的结果

由于棋盘千变万化，但你们对难度的评判不变，所以会有 $T$ 组询问，但 $k$ 相同

输入格式

第一行两个整数 $T, k$

接下来 $T$ 行，每行两个整数 $n, m$ 表示一次询问

输出格式

$T$ 行，每行一个整数表示一次询问的答案

样例

样例输入1

1 2
2 3

样例输出1

24

样例解释1

在 $2 \times 3$ 的棋盘里放 $5$ 个棋子显然可以分成 $4$ 个空位放在角落的和 $2$ 个空位放在中间的情况

对于空位放在角落的，如下所示，$F = 2, W = F^{2} = 4$

$\left[ \begin{aligned} & && \color{red}1\\ & \color{red}2 && \color{blue}2\\ & \color{blue}1 && \color{red}3 \end{aligned} \right] \qquad \left[ \begin{aligned} & && \color{red}1\\ & \color{blue}1 && \color{red}2\\ & \color{red}3 && \color{blue}2 \end{aligned} \right]$

对于空位放在中间的，如下所示，$F = 2, W = F^{2} = 4$

$\left[ \begin{aligned} & \color{red}1 && \color{blue}2\\ & && \color{red}2\\ & \color{blue}1 && \color{red}3 \end{aligned} \right] \qquad \left[ \begin{aligned} & \color{blue}1 && \color{red}1\\ & && \color{red}2\\ & \color{red}3 && \color{blue}2 \end{aligned} \right]$

综上所述，$ans = 4 \times 4 + 2 \times 4 = 24$

样例输入2

4 1
3 3
100 100
500 500
5000 5000

样例输出2

156
148920944
270986094
698833825

样例解释2

自己算

样例输入3

4 10
5 5
20 20
50 50
5000 5000

样例输出3

368861171
393539110
929889380
479679941

样例解释3

自己算

数据范围

对于所有数据满足 $1 \le T, n, m \le 5000, 0 \le k < 998244352$

详细部分分如下：