409755: GYM103729 I Latitude Compressor

"Our world is surrounded by the pale, 6000 kilometres to the north, and even more to the south, east and west. In the Dolorian-era, we discovered the New New World, the piece of reality we're standing on."

"In modern times, it is possible to force dimensions on the pale – we can even compress its latitude, with a permutation generator, bouncing radio waves from one end to the other. Shortening the path."

Now, you got a latitude compressor and you want to evaluate its effect, you can hardly tell how it works, but you know, once you sent a permutation $$$p$$$, you will get the permutation $$$p^m$$$ (it means the product of $$$m$$$ same permutations), $$$m$$$ nanoseconds later.

After sending all the permutations with length $$$n$$$, its effect can be evaluated as the number of different permutations after compressed by the compressor.

Since the answer maybe too large, you just need to output it modulo $$$998244353$$$.

By the way, if you don't know what permutation and the product of permutations is, here is a brief introduction :

A permutation with length $$$n$$$ can be represented as :

$$$$$$ f = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ f(1) & f(2) & \dots & f(n)\\ \end{array} \right) $$$$$$

where $$$f(1), f(2), \dots, f(n)$$$ are integers in $$$[1,n]$$$ and pairwise different.

And the product of two permutation is defined as :

$$$$$$ f\times g = \left( \begin{array}{cccc} 1 & 2 & \dots & n\\ g(f(1)) & g(f(2)) & \dots & g(f(n))\\ \end{array} \right) $$$$$$

One line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50000$$$).

Print a single integer that represents the answer *modulo $$$998244353$$$*.

3 2

3

4 2

12

6 12

145

654 72

922925108

For the first test case, we have $$$n=3,\ m=2$$$.

There are $$$6$$$ different permutations with length $$$3$$$, we present it as $$$f = (f(1), f(2), f(3))$$$, and there square will be:

$$$f = (1,2,3),\quad (1,2,3) \stackrel{f}{\longrightarrow} (1,2,3) \stackrel{f}{\longrightarrow} (1,2,3)$$$

$$$f = (1,3,2),\quad (1,2,3) \stackrel{f}{\longrightarrow} (1,3,2) \stackrel{f}{\longrightarrow} (1,2,3)$$$

$$$f = (2,1,3),\quad (1,2,3) \stackrel{f}{\longrightarrow} (2,1,3) \stackrel{f}{\longrightarrow} (1,2,3)$$$

$$$f = (2,3,1),\quad (1,2,3) \stackrel{f}{\longrightarrow} (2,3,1) \stackrel{f}{\longrightarrow} (3,1,2)$$$

$$$f = (3,1,2),\quad (1,2,3) \stackrel{f}{\longrightarrow} (3,1,2) \stackrel{f}{\longrightarrow} (2,3,1)$$$

$$$f = (3,2,1),\quad (1,2,3) \stackrel{f}{\longrightarrow} (3,2,1) \stackrel{f}{\longrightarrow} (1,2,3)$$$

Then we got $$$3$$$ different permutations after compressed.