Description

Ling is a girl who loves playing games.

In the game, she wants to smelt a rare alloy. To do this, she needs to combine $n$ kinds of metals.

After preparing the ores, she builds $k$ different furnaces. When a furnace starts, it will randomly produce some of these $n$ kinds of metals (and it may also produce nothing).

If we collect the metals produced by all furnaces, and we obtain all $n$ kinds of metals, then we can make the alloy. Mio is curious and says to Ling: "Let me test you. How many different outcomes can produce the alloy?" Ling can quickly solve this simple problem. Can you compute the result?

The answer may be very large. Please output it modulo $998244353$ (that is, the remainder after division by $998244353$).

Input Format

Input one line with two positive integers $n, k$.

Output Format

Output one line with one integer, representing the answer.

2 2

9

4 5

923521

233 123

81633405

Hint

[Explanation of Sample 1]
For all successful outcomes, the metals produced by the two furnaces are shown in the table below:

There are $9$ outcomes in total, so the answer is $9$.

[Constraints]
For $30\%$ of the testdata, $1 \le n, k \le 10$.
For $80\%$ of the testdata, $1 \le n, k \le 10^6$.
For $100\%$ of the testdata, $1 \le n, k \le 10^9$.

Translated by ChatGPT 5