P - ボール 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 5 点

問題文

整数 N, M, K が与えられます。m = 1, 2, \dots, M について次の問題を解いてください。

1 から N までの番号のついた N 個のボールと、0 から m までの番号のついた m+1 個の箱があります。
箱 0 にはボールが K 個まで入ります。それ以外の箱に入るボールの個数の上限はありません。
箱に N 個全てのボールを入れる方法の個数を 998244353 で割った余りを求めてください。ただし、2 つのボールを入れる方法は、入っている箱の番号が 2 つの方法の間で異なるボールが存在する時に別々に数えます。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq N
  • 入力される値は全て整数

入力

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

N M K

出力

M 行出力せよ。i 行目には m=i の時の答えを出力せよ。

入力例 1

3 2 1

出力例 1

4
20

m=1 の場合を考えます。条件を満たすボールの入れ方は次の 4 通りです。

  • 箱 1 にボール 1,2,3 を入れる。
  • 箱 0 にボール 1 を、箱 1 にボール 2,3 を入れる。
  • 箱 0 にボール 2 を、箱 1 にボール 1,3 を入れる。
  • 箱 0 にボール 3 を、箱 1 にボール 1,2 を入れる。

入力例 2

12345 5 6789

出力例 2

583034791
982161077
613932842
770852810
194914198

Score: 5 points

Problem Statement

You are given integers N, M, K.
For each m = 1, 2, \dots, M, solve the following problem:

There are N balls numbered 1 through N, and m+1 boxes numbered 0 through m.
Box 0 can hold at most K balls. The other boxes have no upper limit.
Find the number of ways to place all N balls into the boxes, modulo 998244353.
Two placements are considered different if there exists at least one ball that is placed in different boxes between the two placements.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq N
  • All input values are integers

Input

The input is given from standard input in the following format:

N M K

Output

Print M lines. On the i-th line, output the answer for m = i.

Sample Input 1

3 2 1

Sample Output 1

4
20

Consider the case m=1. There are 4 valid placements of the balls:

  • Put balls 1,2,3 into box 1.
  • Put ball 1 into box 0, and balls 2,3 into box 1.
  • Put ball 2 into box 0, and balls 1,3 into box 1.
  • Put ball 3 into box 0, and balls 1,2 into box 1.

Sample Input 2

12345 5 6789

Sample Output 2

583034791
982161077
613932842
770852810
194914198