7333: ABC237 —— F - |LIS| = 3
[Creator : ]
Description
Find the number of sequences that satisfy all of the conditions below, modulo 998244353.
A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.
- 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.
Input
Input is given from Standard Input in the following format:
$N\ M$
$N\ M$
Output
Print the answer.
Constraints
$3≤N≤1000$
$3 \leq M \leq 10$
All values in input are integers.
$3 \leq M \leq 10$
All values in input are integers.
Sample 1 Input
4 5
Sample 1 Output
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.
On the other hand, (4,4,1,5) do not, because its longest increasing subsequence has the length of 2.
Sample 2 Input
3 4
Sample 2 Output
4
Sample 3 Input
111 3
Sample 3 Output
144980434