7356: ABC275 —— E - Sugoroku 4
[Creator : ]
Description
Takahashi is playing sugoroku, a board game.
The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.
The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.
For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 44 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.
When Takahashi arrives at square N, he wins and the game ends.
Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.
Here, there is a unique integer z between 0 and 998244352 such that $xz \equiv y \pmod{998244353}$. Print this z.
The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.
The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.
For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 44 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.
When Takahashi arrives at square N, he wins and the game ends.
Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.
- How to print a probability modulo 998244353
Here, there is a unique integer z between 0 and 998244352 such that $xz \equiv y \pmod{998244353}$. Print this z.
Input
The input is given from Standard Input in the following format:
$N\ M\ K$
$N\ M\ K$
Output
Print the answer.
Constraints
$M≤N≤1000$
$1 \leq M \leq 10$
$1 \leq K \leq 1000$
All values in the input are integers.
$1 \leq M \leq 10$
$1 \leq K \leq 1000$
All values in the input are integers.
Sample 1 Input
2 2 1
Sample 1 Output
499122177
Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is $\frac{1}{2}$.
We have $2\times 499122177 \equiv 1 \pmod{998244353}$, so the answer to be printed is 499122177.
We have $2\times 499122177 \equiv 1 \pmod{998244353}$, so the answer to be printed is 499122177.
Sample 2 Input
10 5 6
Sample 2 Output
184124175
Sample 3 Input
100 1 99
Sample 3 Output
0