P8557 Alchemy (Alchemy)

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 one line with two positive integers $n, k$.

Output one line with one integer, representing the answer.

[Explanation of Sample 1] For all successful outcomes, the metals produced by the two furnaces are shown in the table below: | No. 1 | No. 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 $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