| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 37 | 32 | 30 | 88.235% |
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ドル ≤ a_i ≤ 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 ≤ j ≤ 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 ai and does not leave empty-handed, for all 1ドル ≤ i ≤ 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ドル ≤ M ≤ N ≤ 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$.
4 3
50
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)$.
10 1
10
All starting sequences are fair.
2 2
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.