P15625 [ICPC 2022 Jakarta R] Sharing Bread

There are $N$ toasters, numbered from $1$ to $N$, from left to right. Initially, each toaster has a single piece of bread in it. There are $M$ people, numbered from $1$ to $M$, who are one by one looking for bread among the toasters, starting from person $1$, person $2$, and so on. Person $i$ starts looking from toaster $a_i$ ($1 \leq a_i \leq N$) and keeps going right until they found a toaster with a piece of bread in it. In other words, person $i$ is looking for the smallest $j$ such that $a_i \leq j \leq N$ and toaster $j$ contains bread. If such a toaster exists, then person $i$ will take the bread from that toaster and leave; the toaster becomes empty afterward. If such a toaster does not exist, then person $i$ will leave empty-handed. A starting sequence $(a_1, a_2, \cdots, a_M)$ is **fair** if person $i$ starts looking from toaster $a_i$ and does not leave empty-handed, for all $1 \leq i \leq M$. Out of all $N^M$ possible starting sequences, determine how many of them are fair modulo $998\,244\,353$.

Input consists of two integers $N$ $M$ ($1 \leq M \leq N \leq 200\,000$) in a single line representing the number of toasters and the number of people, respectively.

Output an integer in a single line representing the number of fair starting sequence modulo $998\,244\,353$.

#### Explanation for the sample input/output #1 One of the possible fair starting sequences is $(4, 2, 2)$. First, person $1$ starts looking from toaster $4$ and takes the bread from toaster $4$. Then, person $2$ starts looking from toaster $2$ and takes the bread from toaster $2$. Finally, person $3$ will start looking from toaster $2$, which is currently empty. Person $3$ moves to toaster $3$ and takes the bread from toaster $3$. Since each person gets a piece of bread, the starting sequence $(4, 2, 2)$ is fair. Another example of fair starting sequences are $(1, 1, 1)$, $(1, 1, 2)$, $(2, 3, 4)$, and $(2, 2, 2)$. Some of the possible starting sequences that are not fair are $(3, 3, 3)$, $(3, 4, 3)$, $(4, 4, 1)$, and $(4, 4, 4)$. #### Explanation for the sample input/output #2 All starting sequences are fair. #### Explanation for the sample input/output #3 The only starting sequence that is **not fair** is $(2,2)$. Person $1$ starts looking from toaster $2$ and takes the bread from toaster $2$. Then, person $2$ starts looking from toaster $2$, which is currently empty. Since there is no more toaster to the right of toaster $2$, person $2$ will leave empty-handed.