AT_abc167_e [ABC167E] Colorful Blocks

[problemUrl]: https://atcoder.jp/contests/abc167/tasks/abc167_e $ N $ 個のブロックが横一列に並んでいます。このブロック列に色を塗ります。 $ 2 $ つのブロック列の塗り方が異なるとは、あるブロックが存在して、そのブロックが異なる色で塗られていることと定義します。 次の条件を満たすブロック列の塗り方が何通りあるか求めてください。 - 各ブロックを色 $ 1 $ から色 $ M $ までのいずれか一色で塗る。使わない色があってもよい。 - 隣り合うブロックの組であって同じ色で塗られている組は、 $ K $ 組以下である。 ただし、答えは非常に大きくなる場合があるので、 $ 998244353 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $

答えを出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \leq\ N,\ M\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ K\ \leq\ N\ -\ 1 $ ### Sample Explanation 1 ブロック列の塗り方を色を書き並べた文字列で表すと、条件を満たすブロック列の色の塗り方は、`112` , `121`, `122`, `211`, `212`, `221` です。