/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個のブロックが横一列に並んでいます。このブロック列に色を塗ります。
2 つのブロック列の塗り方が異なるとは、あるブロックが存在して、そのブロックが異なる色で塗られていることと定義します。
次の条件を満たすブロック列の塗り方が何通りあるか求めてください。
- 各ブロックを色 1 から色 M までのいずれか一色で塗る。使わない色があってもよい。
- 隣り合うブロックの組であって同じ色で塗られている組は、 K 組以下である。
ただし、答えは非常に大きくなる場合があるので、 998244353 で割った余りを出力してください。
制約
- 入力は全て整数
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
3 2 1
出力例 1
6
ブロック列の塗り方を色を書き並べた文字列で表すと、条件を満たすブロック列の色の塗り方は、112 , 121, 122, 211, 212, 221 です。
入力例 2
100 100 0
出力例 2
73074801
入力例 3
60522 114575 7559
出力例 3
479519525
Score : 500 points
Problem Statement
There are N blocks arranged in a row. Let us paint these blocks.
We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.
Find the number of ways to paint the blocks under the following conditions:
- For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.
- There may be at most K pairs of adjacent blocks that are painted in the same color.
Since the count may be enormous, print it modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
3 2 1
Sample Output 1
6
The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.
Sample Input 2
100 100 0
Sample Output 2
73074801
Sample Input 3
60522 114575 7559
Sample Output 3
479519525