题目描述
Problem Description
Ling is a girl who loves playing games.
In the game, she wants to create a rare alloy, which requires $n$ types of metals to synthesize.
After preparing the ores, she built $k$ different furnaces. When a furnace is activated, it randomly produces some of these $n$ types of metals (or possibly none).
If the metals produced by each furnace are collected and all $n$ types of metals are obtained, the alloy can be created. Mio is curious and asks Ling, "I'll test you: how many scenarios can result in creating the alloy?" Ling quickly solves this simple problem, but can you calculate the result?
The answer might be very large, so output it modulo $998244353$ (i.e., the remainder when divided by $998244353$).
Input Format
The input consists of a single line with two positive integers $n, k$.
Output Format
Output a single integer, which is the answer.
Sample Input and Output
Sample Input #1
2 2
Sample Output #1
9
Sample Input #2
4 5
Sample Output #2
923521
Sample Input #3
233 123
Sample Output #3
81633405
Notes
Sample Explanation for Sample #1
For all successful scenarios, the metals in the two furnaces are as follows:
| Furnace 1 | Furnace 2 |
|---|---|
| $\varnothing$ | $\{1,2\}$ |
| $\{1\}$ | $\{2\}$ |
| $\{1\}$ | $\{1,2\}$ |
| $\{2\}$ | $\{1\}$ |
| $\{2\}$ | $\{1,2\}$ |
| $\{1,2\}$ | $\varnothing$ |
| $\{1,2\}$ | $\{1\}$ |
| $\{1,2\}$ | $\{2\}$ |
| $\{1,2\}$ | $\{1,2\}$ |
There are a total of $9$ scenarios, hence the answer is $9$.
Data Range
For $30\%$ of the data, $1 \le n, k \le 10$;
For $80\%$ of the data, $1 \le n, k \le 10^6$;
For $100\%$ of the data, $1 \le n, k \le 10^9$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分