配点 : $600$ 点

問題文

$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)$ で置き換える．
• $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$ で割った余りを求めてください．

制約

• $1 \leq N, M \leq 5000$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

出力

全ての数列に対する $f(A)$ の和を $998244353$ で割った余りを出力せよ．

2 3

15

$3 ^ 2 = 9$ 通りの数列と，それに対する $f$ の値は以下の通りです．

• $A = (1, 1)$ のとき，$(l = 1, r = 2, v = 1)$ として $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)$ として $1$ 回の操作で可能なので，$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)$ として $1$ 回の操作で可能なので，$f(A) = 1$ です．

これらの和は $3 \times 1 + 6 \times 2 = 15$ です．

3 2

15

34 56

649717324