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 翻译