双六 4

题目描述

高桥君正在玩双六(一种棋盘游戏)。

棋盘上有 $N+1$ 个方格,编号为 $0$ 到 $N$。 高桥君从方格 $0$ 出发,目标是方格 $N$。

游戏使用一个轮盘,上面有 $M$ 个数字 $1$ 到 $M$,每个数字出现的概率相等。 高桥君转动轮盘,并按轮盘所示的数字前进相应的格数。如果前进后超过方格 $N$,则在方格 $N$ 处掉头,返回多出的格数。

例如,设 $N=4$,高桥君在方格 $3$。如果轮盘显示 $4$,则超过方格 $4$ 的格数为 $3+4-4=3$。因此,他从方格 $4$ 往回走三格,到达方格 $1$。

当高桥君到达方格 $N$ 时,他就获胜,游戏结束。

求高桥君在最多可以转动 $K$ 次轮盘的条件下获胜的概率,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$ $K$

输出格式

输出答案。

样例

2 2 1

499122177

高桥君在转动一次轮盘时,如果显示 $2$ 则获胜。因此获胜概率为 $\frac{1}{2}$。

因为 $2\times 499122177 \equiv 1 \pmod{998244353}$,所以应输出 $499122177$。

10 5 6

184124175

100 1 99

0

数据范围

• $M \le N \le 1000$
• $1 \le M \le 10$
• $1 \le K \le 1000$
• 输入中的所有值均为整数。

提示

可以证明所求概率总是有理数。 另外,在该问题的约束下,当所求概率表示为不可约分数 $\frac{y}{x}$ 时,可以保证 $x$ 不被 $998244353$ 整除。

这里,存在唯一的整数 $z$,满足 $0 \le z \le 998244352$ 且 $xz \equiv y \pmod{998244353}$。输出这个 $z$。