AmShZ Farm

题意翻译

给定 $n,k$，求长度为 $n$ 的“好序列” $\{a\}$ 的贡献和。 “好序列”这样定义：对于 $i\in [1,n]$，$\sum [a_j\ge i]\le n- i+1$ 其贡献定义为每种颜色的出现次数的 $k$ 次幂之和。 $n\le 10^9,k\le 10^5$

题目描述

To AmShZ, all arrays are equal, but some arrays are more-equal than others. Specifically, the arrays consisting of $ n $ elements from $ 1 $ to $ n $ that can be turned into permutations of numbers from $ 1 $ to $ n $ by adding a non-negative integer to each element. Mashtali who wants to appear in every problem statement thinks that an array $ b $ consisting of $ k $ elements is compatible with a more-equal array $ a $ consisting of $ n $ elements if for each $ 1 \le i \le k $ we have $ 1 \le b_i \le n $ and also $ a_{b_1} = a_{b_2} = \ldots = a_{b_k} $ . Find the number of pairs of arrays $ a $ and $ b $ such that $ a $ is a more-equal array consisting of $ n $ elements and $ b $ is an array compatible with $ a $ consisting of $ k $ elements modulo $ 998244353 $ . Note that the elements of $ b $ are not necessarily distinct, same holds for $ a $ .

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ k $ $ (1 \le n \le 10^9 , 1 \le k \le 10^5) $ .

输出格式

Print a single integer — the answer to the problem modulo $ 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

说明

There are eight possible pairs for the second example: 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\} $