配点 : $500$ 点

問題文

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

この双六には $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$ で求めてください。

制約

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

入力

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

$N$ $M$ $K$

出力

答えを出力せよ。

2 2 1

499122177

$1$ 回ルーレットを回してゴールできるのは、ルーレットで $2$ が出るときです。よってゴールできる確率は $\frac{1}{2}$ です。

このとき、$2\times 499122177 \equiv 1 \pmod{998244353}$ が成り立つので、答えとして $499122177$ を出力してください。

10 5 6

184124175

100 1 99

0