/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N の番号がついた N+1 個のマスがあります。 高橋君はマス 0 からスタートし、マス N を目指します。
この双六では、1 から M までの M 種類の目が等確率で出るルーレットを使います。 高橋君はルーレットを回して出た目の数だけ進みます。もし、マス N を超えて進むことになる場合、マス N を超えた分だけ引き返します。
例えば、 N=4 で高橋君がマス 3 にいるとき、ルーレットを回して出た目が 4 の場合は、マス 4 を 3+4-4=3 マス超えてしまいます。そのため、 3 マスだけマス 4 から引き返し、マス 1 に移動します。
高橋君がマス N に到達するとゴールとなり、双六を終了します。
高橋君がルーレットを K 回まで回す時、ゴールできる確率を \text{mod } 998244353 で求めてください。
確率 \text{mod } 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
2 2 1
出力例 1
499122177
1 回ルーレットを回してゴールできるのは、ルーレットで 2 が出るときです。よってゴールできる確率は \frac{1}{2} です。
このとき、2\times 499122177 \equiv 1 \pmod{998244353} が成り立つので、答えとして 499122177 を出力してください。
入力例 2
10 5 6
出力例 2
184124175
入力例 3
100 1 99
出力例 3
0
Score : 500 points
Problem Statement
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 4 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
It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction \frac{y}{x}, it is guaranteed that x is not divisible by 998244353.
Here, there is a unique integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353}. Print this z.
Constraints
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 2 1
Sample Output 1
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.
Sample Input 2
10 5 6
Sample Output 2
184124175
Sample Input 3
100 1 99
Sample Output 3
0