题目描述

高橋君は双六で遊んでいます。

この双六には $0$ から $N$ の番号がついた $N+1$ 個のマスがあります。 高橋君はマス $0$ からスタートし、マス $N$ を目指します。

この双六では、$1$ から $M$ までの $M$ 種類の目が等確率で出るルーレットを使います。 高橋君はルーレットを回して出た目の数だけ進みます。もし、マス $N$ を超えて進むことになる場合、マス $N$ を超えた分だけ引き返します。

例えば、 $N=4$ で高橋君がマス $3$ にいるとき、ルーレットを回して出た目が $4$ の場合は、マス $4$ を $3+4-4=3$ マス超えてしまいます。そのため、 $3$ マスだけマス $4$ から引き返し、マス $1$ に移動します。

高橋君がマス $N$ に到達するとゴールとなり、双六を終了します。

高橋君がルーレットを $K$ 回まで回す時、ゴールできる確率を $\text{mod\ }\ 998244353$ で求めてください。

確率 $\text{mod\ }\ 998244353$ の定義この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。

このとき $xz\ \equiv\ y\ \pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の整数 $z$ が一意に定まります。この $z$ を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$

输出格式

答えを出力せよ。

题目大意

maze 在一个有 $N+1$ 个格子的棋盘上玩游戏，棋盘上的编号从 $0$ 到 $N$，初始在编号 $0$ 出有一枚棋子。

在一轮游戏中，maze 会随机选择 $1$ 到 $M$ 中的一个数$a$，并将棋子向 $N$ 处移动 $a$ 个格子。如果移动 $a$ 个格子会超过 $N$ ，则会在 $N$ 处掉头向 $0$ 移动剩下的步数。

举个例子：当 $N=4$， $a=4$ ，且 maze 当前在编号为 $3$ 的格子处，则到达 $N$ 时还有 $3$ 步没有走完，会向编号为 $1$ 的格子走 $3$ 步，最终到达编号为 $1$ 的格子处。

若一轮移动完后最终到达编号为 $N$ 的格子，那么游戏会立即结束。现在你需要求出在不多于 $k$ 轮游戏中结束游戏的概率，对 $998244353$ 取模。

2 2 1

499122177

10 5 6

184124175

100 1 99

0

提示

制約

• $M\ \leq\ N\ \leq\ 1000$
• $1\ \leq\ M\ \leq\ 10$
• $1\ \leq\ K\ \leq\ 1000$
• 入力は全て整数

Sample Explanation 1

$1$ 回ルーレットを回してゴールできるのは、ルーレットで $2$ が出るときです。よってゴールできる確率は $\frac{1}{2}$ です。 このとき、$2\times\ 499122177\ \equiv\ 1\ \pmod{998244353}$ が成り立つので、答えとして $499122177$ を出力してください。