题目描述

高桥正在玩一个叫做 sugoroku 的棋盘游戏。

游戏棋盘上有 $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$ 取模。

如何输出取模为 $998244353$ 的概率

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

这里，存在一个唯一的整数 $z$，满足 $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