AT_abc237_f [ABC237F] |LIS| = 3
Description
[problemUrl]: https://atcoder.jp/contests/abc237/tasks/abc237_f
以下の条件を全て満たす数列の個数を、$ 998244353 $ で割った余りを求めてください。
- 数列の長さが $ N $
- 数列の各項は $ 1 $ 以上 $ M $ 以下の整数
- 最長増加部分列の長さがちょうど $ 3 $
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $
Output Format
答えを出力せよ。
Explanation/Hint
### 注記
数列の**部分列**とは、数列から $ 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 $ で割った余りを求めてください。