← 返回题目列表

AtCoder · arc163_f

F. 许多日益增加的问题

中文机器翻译题面 查看原题

分数: 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