|LIS| = 3

题目描述

请计算满足以下所有条件的数列个数，并对 $998244353$ 取模输出：

• 数列长度为 $N$；
• 数列中的每一项都是 $1$ 到 $M$ 之间的整数；
• 数列的最长上升子序列长度恰好为 $3$。

注记

一个数列的子序列，是指从原数列中删除 $0$ 个或多个元素后，将剩余元素按原顺序连接得到的数列。

例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，而 $(20,10)$ 不是 $(10,20,30)$ 的子序列。

一个数列的最长上升子序列，是指所有严格单调递增子序列中长度最大的子序列。

输入格式

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

N M

输出格式

输出答案对 $998244353$ 取模后的结果。

数据范围

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

样例

样例输入 1

4 5

样例输出 1

135

样例输入 2

3 4

样例输出 2

4

样例输入 3

111 3

样例输出 3

144980434

样例说明

样例 1 中，$(3,4,1,5)$ 是一个满足条件的数列。另一方面，$(4,4,1,5)$ 的最长上升子序列长度为 $2$，因此不满足条件。

样例 3 要求输出对 $998244353$ 取模后的结果。