/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
4 5
出力例 1
135
例えば (3,4,1,5) は条件を満たす数列です。
一方 (4,4,1,5) は最長増加部分列の長さが 2 なので条件を満たしません。
入力例 2
3 4
出力例 2
4
入力例 3
111 3
出力例 3
144980434
998244353 で割った余りを求めてください。
Score : 500 points
Problem Statement
Find the number of sequences that satisfy all of the conditions below, modulo 998244353.
- The length is N.
- Each of the elements is an integer between 1 and M (inclusive).
- Its longest increasing subsequence has the length of exactly 3.
Notes
A subsequence of a sequence is the result of removing zero or more elements from it and concatenating the remaining elements without changing the order. For example, (10,30) is a subsequence of (10,20,30), while (20,10) is not a subsequence of (10,20,30).
A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.
Constraints
- 3 \leq N \leq 1000
- 3 \leq M \leq 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
4 5
Sample Output 1
135
One sequence that satisfies the conditions is (3,4,1,5).
On the other hand, (4,4,1,5) do not, because its longest increasing subsequence has the length of 2.
Sample Input 2
3 4
Sample Output 2
4
Sample Input 3
111 3
Sample Output 3
144980434
Find the count modulo 998244353.