分数: 500 点
问题陈述
高桥正在玩双六,一种棋盘游戏。
董事会有 N+1 正方形,编号 0 to N。 高桥从广场开始 0 并前往正方形 N.
该游戏使用轮盘赌轮 M 号码来自 1 to M 以相同的概率出现。 高桥旋转轮盘并按照轮盘指示的方格数移动。如果这会让他超越广场 N,他在广场转身 N 并返回过多的方格数。
例如,假设 N=4 高桥在广场 3。如果车轮显示 4,超出方格数量过多 4 is 3+4-4=3。因此,他从正方形向后退了三格 4 并到达广场 1.
当高桥到达广场时 N,他获胜,游戏结束。
求概率,模 998244353,高桥最多可以旋转轮盘时获胜 K 次。
如何打印概率模数 998244353
可以证明,求的概率总是有理数。 另外,在该问题的约束下,当寻求的概率表示为不可约分数时 \frac{y}{x},保证 x 不能被整除 998244353.
这里有一个唯一的整数 z 之间 0 和 998244352 这样 xz \equiv y \pmod{998244353}。打印此内容 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
如果轮盘显示,高桥一转获胜 2。因此,获胜的概率为 \frac{1}{2}.
我们有 2\times 499122177 \equiv 1 \pmod{998244353},所以要打印的答案是 499122177.
示例输入 2
10 5 6
示例输出 2
184124175
示例输入 3
100 1 99
示例输出 3
0