E - Sugoroku 4
当前没有测试数据。
E - Sugoroku 4
得分：500分
问题描述
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$。
约束
- $M \leq N \leq 1000$
- $1 \leq M \leq 10$
- $1 \leq K \leq 1000$
- 输入中的所有值都为整数。
输入
从标准输入中以如下格式给出：
输出
输出答案。
2 2 1
499122177
如果轮盘显示$2$，Takahashi在一次旋转中获胜。因此，获胜的概率为$\frac{1}{2}$。
我们有$2\times 499122177 \equiv 1 \pmod{998244353}$，因此要输出的答案是$499122177$。
10 5 6
184124175
100 1 99
0