题目描述

对于由 $1$ 到 $M$ 之间的整数构成的长度为 $N$ 的数列 $A$，定义 $f(A)$ 如下：

• 存在一个长度为 $N$ 的数列 $X$，初始时所有元素均为 $0$。$f(A)$ 表示通过以下操作将 $X$ 变为 $A$ 所需的最少操作次数。
  • 可以指定 $1 \leq l \leq r \leq N$ 和 $1 \leq v \leq M$，将 $l \leq i \leq r$ 的所有 $X_i$ 替换为 $\max(X_i, v)$。

作为 $A$ 的所有可能的数列共有 $M^N$ 种。请计算所有这些数列对应的 $f(A)$ 之和，并对 $998244353$ 取模。

输入格式

输入从标准输入读取，格式如下：

$N$ $M$

输出格式

输出所有数列对应的 $f(A)$ 之和对 $998244353$ 取模的结果。

样例 1

输入

2 3

输出

15

样例 2

输入

3 2

输出

15

样例 3

输入

34 56

输出

649717324

说明/提示

限制条件

• $1 \leq N, M \leq 5000$
• 输入均为整数

样例解释 1

共有 $3^2 = 9$ 种数列，对应的 $f$ 值如下：

• 当 $A = (1, 1)$ 时，只需一次操作 $(l=1, r=2, v=1)$，所以 $f(A) = 1$。
• 当 $A = (1, 2)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=2, r=2, v=2)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (1, 3)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=2, r=2, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (2, 1)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=1, r=1, v=2)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (2, 2)$ 时，只需一次操作 $(l=1, r=2, v=2)$，所以 $f(A) = 1$。
• 当 $A = (2, 3)$ 时，先操作 $(l=1, r=2, v=2)$，再操作 $(l=2, r=2, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (3, 1)$ 时，先操作 $(l=1, r=2, v=1)$，再操作 $(l=1, r=1, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (3, 2)$ 时，先操作 $(l=1, r=2, v=2)$，再操作 $(l=1, r=1, v=3)$，共需 $2$ 次操作，所以 $f(A) = 2$。
• 当 $A = (3, 3)$ 时，只需一次操作 $(l=1, r=2, v=3)$，所以 $f(A) = 1$。

这些 $f(A)$ 的和为 $3 \times 1 + 6 \times 2 = 15$。

由 ChatGPT 4.1 翻译