AT_agc021_f.[AGC021F] Trinity

有一个纵向 $N$ 行、横向 $M$ 列的网格。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。特别地，最左上角的格子为 $(1,1)$，最右下角的格子为 $(N,M)$。高桥君将若干（可以为 $0$ 个）格子涂成黑色，其余格子为白色。

定义长度为 $N$ 的数列 $A$，长度为 $M$ 的数列 $B$ 和 $C$，如下所示：

• $A_i\ (1\leq i\leq N)$：第 $i$ 行中被涂黑的格子的最小列号 $j$（如果不存在，则为 $M+1$）。
• $B_i\ (1\leq i\leq M)$：第 $i$ 列中被涂黑的格子的最小行号 $k$（如果不存在，则为 $N+1$）。
• $C_i\ (1\leq i\leq M)$：第 $i$ 列中被涂黑的格子的最大行号 $k$（如果不存在，则为 $0$）。

请计算所有可能的三元组 $(A,B,C)$ 的数量，并对 $998244353$ 取模后输出。

输入为一行，包含两个整数 $N$ 和 $M$。

输出所有可能的 $(A,B,C)$ 组数对 $998244353$ 取模的结果。

注意

本题提交的源代码大小限制为 $20000$ 字节。超出该长度的提交将被判为无效，请注意。

数据范围

• $1 \leq N \leq 8000$
• $1 \leq M \leq 200$
• $N,M$ 均为整数

部分分

• 对于满足 $N \leq 300$ 的数据集，答对可得 $1500$ 分。

样例说明 1

当 $N=2$ 时，可以由 $B_i,C_i$ 的信息唯一确定每一列黑色格子的分布。对于每个 $i$，$(B_i,C_i)$ 的组合有 $(1,1),(1,2),(2,2),(3,0)$ 共 $4$ 种，因此答案为 $4^M=64$ 种。

由 ChatGPT 4.1 翻译