题目描述

以下の条件を全て満たす数列の個数を、$998244353$ で割った余りを求めてください。

• 数列の長さが $N$
• 数列の各項は $1$ 以上 $M$ 以下の整数
• 最長増加部分列の長さがちょうど $3$

输入格式

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

$N$ $M$

输出格式

答えを出力せよ。

题目大意

请求出满足以下条件的数列的个数：

• 数列长度为 $N$

• 数列各项为 $1$ 以上 $M$ 以下的整数

• 最长增加部分列长度正好为 $3$

请输出答案对 $998244353$ 取模的结果。

4 5

135

3 4

4

111 3

144980434

提示

注記

数列の部分列とは、数列から $0$ 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。
例えば、$(10,30)$ は $(10,20,30)$ の部分列ですが、$(20,10)$ は $(10,20,30)$ の部分列ではありません。

数列の最長増加部分列とは、数列の狭義単調増加な部分列のうち、長さが最大のもののことをいいます。

制約

• $3\ \leq\ N\ \leq\ 1000$
• $3\ \leq\ M\ \leq\ 10$
• 入力は全て整数である

Sample Explanation 1

例えば $(3,4,1,5)$ は条件を満たす数列です。 一方 $(4,4,1,5)$ は最長増加部分列の長さが $2$ なので条件を満たしません。

Sample Explanation 3

$998244353$ で割った余りを求めてください。