分数: 600 点
问题陈述
对于序列 A 长度 N 由之间的整数组成 1 和 M (包含),让我们定义 f(A) 如下:
- 我们有一个序列 X 长度 N,其中每个元素最初都是 0. f(A) 是进行操作所需的最少操作数 X 等于 A 通过重复以下操作:
- 指定 1 \leq l \leq r \leq N 和 1 \leq v \leq M,然后替换 X_i 与 \max(X_i, v) 对于每个 l \leq i \leq r.
求总和,模 998244353,属于 f(A) 总的来说 M^N 序列可以是 A.
约束
- 1 \leq N, M \leq 5000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
输出
打印总和 f(A) 所有序列 A,模数 998244353.
示例输入 1
2 3
示例输出 1
15
的 3 ^ 2 = 9 序列和值 f 如下:
- 对于 A = (1, 1),我们可以制作 X 等于一次操作 (l = 1, r = 2, v = 1),所以 f(A) = 1.
- 对于 A = (1, 2),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 1) 和 (l = 2, r = 2, v = 2),所以 f(A) = 2.
- 对于 A = (1, 3),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 1) 和 (l = 2, r = 2, v = 3),所以 f(A) = 2.
- 对于 A = (2, 1),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 1) 和 (l = 1, r = 1, v = 2),所以 f(A) = 2.
- 对于 A = (2, 2),我们可以制作 X 等于一次操作 (l = 1, r = 2, v = 2),所以 f(A) = 1.
- 对于 A = (2, 3),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3),所以 f(A) = 2.
- 对于 A = (3, 1),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 1) 和 (l = 1, r = 1, v = 3) so f(A) = 2.
- 对于 A = (3, 2),我们可以制作 X 等于它与两个操作 (l = 1, r = 2, v = 2) 和 (l = 1, r = 1, v = 3),所以 f(A) = 2.
- 对于 A = (3, 3),我们可以制作 X 等于一次操作 (l = 1, r = 2, v = 3),所以 f(A) = 1.
这些值的总和是 3 \times 1 + 6 \times 2 = 15.
示例输入 2
3 2
示例输出 2
15
示例输入 3
34 56
示例输出 3
649717324