配点 : 300 点
問題文
Tapris 喜欢数字序列。
Tapris-chan的当前长度是 1 序列 使用 A = (1) 。 来自
塔普里斯酱是 为 A 选择以下操作之一。 我决定重复 N 次。下面是编号顺序 从之前 A 从以前开始 i~(1 \leq i \leq |A|) 第一个元素 您可以将其更改为 a_i 。 在
- A 结束时 输出为 1 或 至少 M 一个整数
- 1 \leq i < |A| 对于 i 该值应乘以 1 选择一项。 满足a_i < x < a_{i + 1} 或 至少 a_i > x > a_{i + 1} 条件的整数 在 x 该值应乘以 a_i 和 按字典顺序比较 a_{i + 1} 之间添加
i 第一次操作后的编号顺序 A 该值应乘以 S_i 。 在
数字序列 可以 S_1, S_2, \ldots, S_N 的事物类型数量为 除以 998244353 请求出除以后的余数。
制約
- 1 \leq N \leq 3000
- 2 \leq M \leq 10^8
入力
输入是按以下格式从标准输入给出的。
N M
出力
数字序列 可以 S_1, S_2, \ldots, S_N 的事物类型数量为 除以 998244353 的余数。 请输出
入力例 1
2 3
出力例 1
5
第一次操作 添加 A 结束时 输出为 3 添加A = (1, 3) 。 对于
下一步 砍掉 2 关于第二次操作 A 可以得到第 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) 如果
可以得到第 4 没错。因此答案是 请打印除以 5 。 对于
入力例 2
1024 52689658
出力例 2
654836147
998244353 后的余数。