← 返回题目列表

Codeforces · 1310/E

E. 奇怪的功能

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

让我们将多重集 $$$a$$$ 的函数 $$$f$$$ 定义为 $$$a$$$ 中存在的每个数字出现次数的多重集。

例如,$$$f(\{5, 5, 1, 2, 5, 2, 3, 3, 9, 5\}) = \{1, 1, 2, 2, 4\}$$$。

让我们定义 $$$f^k(a)$$$,将 $$$f$$$ 应用于数组 $$$a$$$ $$$k$$$ 次:$$$f^k(a) = f(f^{k-1}(a)), f^0(a) = a$$$。

例如,$$$f^2(\{5, 5, 1, 2, 5, 2, 3, 3, 9, 5\}) = \{1, 2, 2\}$$$。

给定整数 $$$n、k$$$,并询问函数 $$$f^k(a)$$$ 可以有多少个不同的值,其中 $$$a$$$ 是任意非空数组,其数字大小不超过 $$$n$$$。打印答案以 $$$998\,244\,353$$$ 为模。

输入

输入的第一行也是唯一一行由两个整数 $$$n, k$$$ ($$$1 \le n, k \le 2020$$$) 组成。

输出

打印一个数字 - 函数 $$$f^k(a)$$$ 在所有可能的非空数组上的不同值的数量,且不超过 $$$n$$$ 元素以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3 1

输出 #1

6

输入 #2

5 6

输出 #2

1

输入 #3

10 1

输出 #3

138

输入#4

10 2

输出#4

33