分数: 1100 点
问题陈述
PCT-kun 造成了以下问题。
问题日益增多给你一个长度-N 非负整数序列 A_1,A_2,\dots,A_N。您可以执行以下操作任意次数(可能为零)。
- 选择一个整数 i 这样 1 \le i \le N,并增加或减少 A_i by 1.
你的目标是 A 非减少。找出实现这一目标所需的最少操作数。
认为这个问题太容易放在比赛最后,PCT-kun 修改如下。
许多日益增加的问题有 M^N 整数序列 A 长度 N 其中所有元素都位于 1 和 M,包括在内。求答案的总和 问题日益增多 对于所有这些序列,模 998244353.
解决 许多日益增加的问题.
约束
- 1 \le N,M \le 10^5
输入
输入由标准输入按以下格式给出:
N M
输出
将答案打印至 许多日益增加的问题.
示例输入 1
2 2
示例输出 1
1
让我们解决 问题日益增多 对于所有长度的序列 2 其中所有元素都位于 1 和 2,包括在内。
- 对于 A=(1,1),答案是 0.
- 对于 A=(1,2),答案是 0.
- 对于 A=(2,1),答案是 1.
- 对于 A=(2,2),答案是 0.
因此,最终答案是 0+0+1+0=1.
示例输入 2
6 4
示例输出 2
14668
示例输入 3
163 702
示例输出 3
20728656
示例输入 4
98765 99887
示例输出 4
103564942