分数: 700 点
问题陈述
考虑长度为整数的序列 N: S=(S_1,S_2,\dots,S_N)。 我们称一个序列为 辉煌 如果满足以下所有条件:
-
S_i 是一个(可能为空)整数集,其元素在范围内 [1,M]. (1 \le i \le N)
-
恰好包含在以下之一中的整数数量 S_i 和 S_{i+1} is 1. (1 \le i \le N-1)
我们定义精彩序列的分数 S as \displaystyle \prod_{i=1}^{M} ( 其中的套数 S_1,S_2,\dots,S_N 包括 i.).
查找,取模 998244353,所有可能的精彩序列的分数总和。
约束
- 1 \le N,M \le 2 \times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
2 3
示例输出 1
24
在所有可能的精彩序列中,以下 6 得分为正。
- S_1=\{1,2\},S_2=\{1,2,3\}
- S_1=\{1,3\},S_2=\{1,2,3\}
- S_1=\{2,3\},S_2=\{1,2,3\}
- S_1=\{1,2,3\},S_2=\{1,2\}
- S_1=\{1,2,3\},S_2=\{1,3\}
- S_1=\{1,2,3\},S_2=\{2,3\}
他们的得分均为 4,所以它们的总和是 24.
示例输入 2
12 34
示例输出 2
786334067