← 返回题目列表

Codeforces · 1528/F

F. AmShZ 农场

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

对于 AmShZ 来说,所有数组都是平等的,但有些数组比其他数组更平等。具体来说,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 元素组成的数组可以通过向每个元素添加非负整数来转换为从 $$$1$$$ 到 $$$n$$$ 的数字排列。

Mashtali 想要出现在每个问题陈述中,他认为由 $$$k$$$ 元素组成的数组 $$$b$$$ 与由 $$$n$$$ 元素组成的更相等的数组 $$$a$$$ 兼容,如果对于每个 $$$1 \le i \le k$$$ 我们有 $$$1 \le b_i \le n$$$ 并且 $$$a_{b_1} = a_{b_2} = \ldots = a_{b_k}$$$。

查找数组 $$$a$$$ 和 $$$b$$$ 的对数,使得 $$$a$$$ 是由 $$$n$$$ 元素组成的更相等的数组,而 $$$b$$$ 是与 $$$a$$$ 兼容的数组,由 $$$k$$$ 元素对 $$$998244353$$$ 取模组成。

请注意,$$$b$$$ 的元素不一定不同,$$$a$$$ 也是如此。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1 \le n \le 10^9 , 1 \le k \le 10^5)$$$。

输出

打印一个整数——问题的答案以 $$$998244353$$$ 为模。

示例

输入 #1

1 1

输出 #1

1

输入 #2

2 2

输出 #2

8

输入 #3

5 4

输出 #3

50400

输入#4

20 100

输出#4

807645526

输入 #5

10000000 10000

输出 #5

883232350

注意

第二个示例有八个可能的对:

1. $$$a = \{1, 1\}, b = \{1, 1\}$$$
2. $$$a = \{1, 1\}, b = \{1, 2\}$$$
3. $$$a = \{1, 1\}, b = \{2, 1\}$$$
4. $$$a = \{1, 1\}, b = \{2, 2\}$$$
5. $$$a = \{1, 2\}, b = \{1, 1\}$$$
6. $$$a = \{1, 2\}, b = \{2, 2\}$$$
7. $$$a = \{2, 1\}, b = \{1, 1\}$$$
8. $$$a = \{2, 1\}, b = \{2, 2\}$$$