题目描述

$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 - M$ 的整数组成的，长为 $N$ 的序列 $A$。

对于 $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)$ 之和除以$9982444353$的余数。

输入：两个数 $N$ , $M$。

输出：一个数，为结果。

数据范围: $1 \leq N,M \leq 5000$

2 3

15

3 2

15

34 56

649717324

提示

制約

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

Sample Explanation 1

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