AT_kupc2020_g Counting Angels

タプリス酱喜欢数列。 现在，タプリス酱有一个长度为 $1$ 的数列 $A = (1)$。 她决定对 $A$ 重复进行 $N$ 次以下任意一种操作。下面，记数列 $A$ 从前往后第 $i$（$1 \leq i \leq |A|$）个元素为 $a_i$。 - 在 $A$ 的末尾添加 $1$ 或 $M$。 - 选择一个整数 $i$，满足 $1 \leq i < |A|$。在 $a_i$ 和 $a_{i+1}$ 之间插入一个整数 $x$，使得 $a_i < x < a_{i+1}$ 或 $a_i > x > a_{i+1}$。 第 $i$ 次操作后得到的数列 $A$ 记为 $S_i$。 请你求出所有可能的数列序列 $S_1, S_2, \ldots, S_N$ 的种类数，结果对 $998244353$ 取模。

输入为以下格式，从标准输入读入。 > $N$ $M$

输出所有可能的数列序列 $S_1, S_2, \ldots, S_N$ 的种类数，对 $998244353$ 取模后的结果。

## 限制条件 - $1 \leq N \leq 3000$ - $2 \leq M \leq 10^8$ ## 样例解释 1 首先第一次操作在 $A$ 的末尾添加 $3$，得到 $A = (1, 3)$。接着第二次操作在 $1$ 和 $3$ 之间插入 $2$，得到 $A = (1, 2, 3)$。因此，这样操作后，$S_1 = (1, 3), S_2 = (1, 2, 3)$。 除此之外，还可以有以下情况： - $S_1 = (1, 1), S_2 = (1, 1, 1)$ - $S_1 = (1, 1), S_2 = (1, 1, 3)$ - $S_1 = (1, 3), S_2 = (1, 3, 3)$ - $S_1 = (1, 3), S_2 = (1, 3, 1)$ 共 $5$ 种情况。因此答案为 $5$。 ## 样例解释 2 请输出对 $998244353$ 取模后的结果。 由 ChatGPT 4.1 翻译