E. Ball Dumping Golf
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is one box labeled with each integer from $$$1$$$ to $$$N$$$. Also, for each integer from $$$1$$$ to $$$N$$$, there are $$$M$$$ balls labeled with that integer.

These $$$NM$$$ balls are shuffled and then distributed into the $$$N$$$ boxes, with exactly $$$M$$$ balls placed into each box.

There are $$$\frac{(NM)!}{(M!)^N}$$$ possible ways to place the balls (if all balls are considered distinguishable), and all of these arrangements occur with equal probability.

You will perform operations on these boxes and balls. One operation consists of the following steps.

  1. Choose one box and go in front of that box.
  2. If there is no ball in that box, terminate the operation.
  3. Choose any one ball from that box and discard it outside the box.
  4. Finally, go in front of the box whose label matches the label of the ball most recently discarded, and return to step 2.

Define your score as the number of operations required until all $$$NM$$$ balls have been discarded. You want to minimize this score.

Find the expected value of the score when you act optimally, modulo $$$998244353$$$.

Input

The first line contains $$$N$$$ and $$$M$$$ in this order, separated by spaces. ($$$1\leq N\leq 10^5$$$, $$$1\leq M\leq 100$$$)

Output

Print the answer.

Examples
Input
2 2
Output
166374060
Input
3 1
Output
831870296
Input
100000 100
Output
402978825
Note

For the first example, the possible ball arrangements and the corresponding optimal ways of operating are as follows.

  • Put two balls labeled $$$1$$$ into box $$$1$$$, and two balls labeled $$$2$$$ into box $$$2$$$. ( Probability $$$1/6$$$ )
    • In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out another ball labeled $$$1$$$ and go in front of box $$$1$$$ again. At this point, box $$$1$$$ is empty, so terminate the operation.
    • In the second operation, go in front of box $$$2$$$. From there, take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out another ball labeled $$$2$$$ and go in front of box $$$2$$$ again. At this point, box $$$2$$$ is empty, so terminate the operation.
    • In this case, the minimum achievable score is $$$2$$$.
  • Put one ball labeled $$$1$$$ and one ball labeled $$$2$$$ into each of box $$$1$$$ and box $$$2$$$. ( Probability $$$2/3$$$ )
    • In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. At this point, box $$$1$$$ is empty, so terminate the operation.
    • In this case, the minimum achievable score is $$$1$$$.
  • Put two balls labeled $$$2$$$ into box $$$1$$$, and two balls labeled $$$1$$$ into box $$$2$$$. ( Probability $$$1/6$$$ )
    • In the first operation, go in front of box $$$1$$$. From there, take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. Then take out a ball labeled $$$2$$$ and go in front of box $$$2$$$. Then take out a ball labeled $$$1$$$ and go in front of box $$$1$$$. At this point, box $$$1$$$ is empty, so terminate the operation.
    • In this case, the minimum achievable score is $$$1$$$.

In summary, the minimum score is $$$2$$$ with probability $$$1/6$$$, and the minimum score is $$$1$$$ with probability $$$5/6$$$, so the expected score overall is $$$7/6$$$. Therefore, output $$$166374060$$$, which represents this value modulo $$$998244353$$$.

Definition of expected value modulo $$$998244353$$$

It can be proven that the expected value to be found is always a rational number. Also, under the constraints of this problem, if the expected value is written as a reduced fraction $$$\frac{y}{x}$$$, it is guaranteed that $$$x$$$ is not divisible by $$$998244353$$$.

In this case, there exists a unique integer $$$z$$$ between $$$0$$$ and $$$998244352$$$, inclusive, satisfying $$$xz \equiv y \pmod{998244353}$$$. Output this $$$z$$$.