Score : $500$ points

问题描述

Takahashi 正在玩一款名为 sugoroku 的桌面游戏。

棋盘上有 $N+1$ 个格子，编号从 $0$ 到 $N$。Takahashi 从第 $0$ 号格子出发，目标是到达第 $N$ 号格子。

游戏中使用了一个轮盘，上面有 $M$ 个从 $1$ 到 $M$ 的数字，每个数字出现的概率相等。Takahashi转动轮盘，并按照轮盘指示的数字移动相应的格子数。如果这将导致他超过第 $N$ 号格子，则他在第 $N$ 号格子处掉头，并按超出的格子数返回。

例如，假设 $N=4$ 并且 Takahashi 在第 $3$ 号格子上。如果轮盘显示数字 $4$，则超过第 $4$ 格子的格子数为 $3+4-4=3$。因此，他会从第 $4$ 格子向回走三个格子，最终到达第 $1$ 格子。

当 Takahashi 到达第 $N$ 号格子时，他就赢了，游戏结束。

计算当 Takahashi 最多可以转轮盘 $K$ 次时，他获胜的概率对 $998244353$ 取模的结果。

如何打印概率对 $998244353$ 取模的结果

可以证明所求概率始终是一个有理数。此外，在本题的约束条件下，当所求概率表示为不可约分数 $\frac{y}{x}$ 时，保证 $x$ 不被 $998244353$ 整除。

此时存在一个唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 以及 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:35:26