配点 : $500$ 点

問題文

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

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

注記

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

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

制約

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

入力

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

$N$ $M$

出力

答えを出力せよ。

4 5

135

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

3 4

4

111 3

144980434

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