AT_abc237_f [ABC237F] |LIS| = 3

题目描述

请计算满足以下所有条件的数列数量，结果对 $998244353$ 取模：

• 数列长度为 $N$
• 数列的每个元素是 $1$ 到 $M$ 之间的整数
• 最长递增子序列（LIS）的长度恰好为 $3$

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$

输出格式

输出答案。

输入输出样例 #1

输入 #1

4 5

输出 #1

135

输入输出样例 #2

输入 #2

3 4

输出 #2

4

输入输出样例 #3

输入 #3

111 3

输出 #3

144980434

说明/提示

注释

数列的子序列是指从原数列中删除 $0$ 个或多个元素后，将剩余元素按原顺序连接得到的数列。
例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，而 $(20,10)$ 不是 $(10,20,30)$ 的子序列。

数列的最长递增子序列是指该数列的所有严格单调递增子序列中长度最大的那个。

约束条件

• $3 \leq N \leq 1000$
• $3 \leq M \leq 10$
• 输入均为整数

样例解释 1

例如 $(3,4,1,5)$ 是符合条件的数列。而 $(4,4,1,5)$ 的最长递增子序列长度为 $2$，因此不符合条件。

样例解释 3

请确保结果对 $998244353$ 取模。

翻译由 DeepSeek R1 完成