问题描述

对于长度为$N$，由介于$1$和$M$（含）之间的整数组成的序列$A$，我们定义$f(A)$如下：

• 我们有一个长度为$N$的序列$X$，初始情况下每个元素均为$0$。通过重复执行以下操作来使$X$等于$A$，$f(A)$为所需的最小操作次数：
  • 指定$1\leq l\leq r\leq N$和$1\leq v\leq M$，然后对于每个$l\leq i\leq r$，将$X_i$替换为$\max(X_i, v)$。

求所有可能的$M^N$个序列$A$的$f(A)$之和，模$998244353$。

约束条件

• $1\leq N, M\leq 5000$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$

输出

打印所有序列$A$的$f(A)$之和，模$998244353$。

示例输入1

2 3

示例输出1

15

有$3^2=9$个序列，以及它们的$f$值：

• 对于$A=(1, 1)$，我们可以通过一次操作$(l = 1, r = 2, v = 1)$使$X$等于它，因此$f(A)=1$。
• 对于$A=(1, 2)$，我们可以通过两次操作$(l = 1, r = 2, v = 1)$和$(l = 2, r = 2, v = 2)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(1, 3)$，我们可以通过两次操作$(l = 1, r = 2, v = 1)$和$(l = 2, r = 2, v = 3)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(2, 1)$，我们可以通过两次操作$(l = 1, r = 2, v = 1)$和$(l = 1, r = 1, v = 2)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(2, 2)$，我们可以通过一次操作$(l = 1, r = 2, v = 2)$使$X$等于它，因此$f(A)=1$。
• 对于$A=(2, 3)$，我们可以通过两次操作$(l = 1, r = 2, v = 2)$和$(l = 2, r = 2, v = 3)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(3, 1)$，我们可以通过两次操作$(l = 1, r = 2, v = 1)$和$(l = 1, r = 1, v = 3)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(3, 2)$，我们可以通过两次操作$(l = 1, r = 2, v = 2)$和$(l = 1, r = 1, v = 3)$使$X$等于它，因此$f(A)=2$。
• 对于$A=(3, 3)$，我们可以通过一次操作$(l = 1, r = 2, v = 3)$使$X$等于它，因此$f(A)=1$。

这些值的总和为$3\times 1 + 6\times 2 = 15$.

示例输入2

3 2

示例输出2

15

示例输入3

34 56

示例输出3

649717324