← 返回题目列表

AtCoder · abc237_f

I. 最长递增子序列长度等于三

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

求满足以下所有条件的序列数,取模 998244353.

  • 长度是 N.
  • 每个元素都是介于 1 和 M (含)。
  • 其最长递增子序列的长度恰好为 序列的 3.

注释

A 子序列 长度为 $$$m$$$ 的 是从中删除零个或多个元素并在不改变顺序的情况下连接剩余元素的结果。 例如, (10,30) 是以下序列的子序列 (10,20,30),同时 (20,10) 不是以下的子序列 (10,20,30).

A 最长递增子序列 序列的 是它的 严格 增加具有最大长度的子序列。

约束

  • 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.