409755: GYM103729 I Latitude Compressor

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Latitude Compressortime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

"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) $$$$$$

Input

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

Output

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

ExamplesInput
3 2
Output
3
Input
4 2
Output
12
Input
6 12
Output
145
Input
654 72
Output
922925108
Note

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.

加入题单

上一题 下一题 算法标签: