AT_abc275_e [ABC275E] Sugoroku 4

[problemUrl]: https://atcoder.jp/contests/abc275/tasks/abc275_e 高橋君は双六で遊んでいます。 この双六には $ 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 $

答えを出力せよ。

### 制約 - $ 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 $ を出力してください。