最长上升子序列长度恰好为 3

题目描述

求满足以下全部条件的序列个数,对 $998244353$ 取模。

• 长度为 $N$。
• 每个元素都是 $1$ 到 $M$(含端点)之间的整数。
• 其最长上升子序列的长度恰好为 $3$。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$

输出格式

输出答案。

样例

4 5

135

满足条件的序列之一为 $(3,4,1,5)$。

另一方面,$(4,4,1,5)$ 不满足条件,因为其最长上升子序列的长度为 $2$。

3 4

4

111 3

144980434

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

数据范围

• $3 \le N \le 1000$
• $3 \le M \le 10$
• 输入中的所有值均为整数。

提示

• 序列的子序列是指删除其中 0 个或多个元素后,将剩余元素按原顺序拼接得到的结果。例如 $(10,30)$ 是 $(10,20,30)$ 的子序列,而 $(20,10)$ 不是 $(10,20,30)$ 的子序列。
• 一个序列的最长上升子序列是其长度最长的严格上升子序列。