問題文

$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$ で割った余りを求めてください．

制約

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

入力

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

$N$ $M$

出力

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

入力例 1

2 3

出力例 1

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$ です．

入力例 2

3 2

出力例 2

15

入力例 3

34 56

出力例 3

649717324