D - Blue and Red Balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

K 個の青いボールと N-K 個の赤いボールがあります。同じ色のボールは区別が不可能です。すぬけ君と高橋君はこれらのボールで遊んでいます。

まず、すぬけ君が、N 個のボールを左から右に一列に並べます。

次に、高橋君は、これらのうち K 個の青いボールのみを回収します。高橋君は、1 回の操作で連続して並ぶ青いボールを何個でも回収することができます。高橋君は、常に K 個の青いボールを回収するのにかかる操作の回数が最小になるように行動します。

K 個の青いボールを回収するために高橋君がちょうど i 回操作をする必要があるボールの並べ方は何通りあるでしょうか。 1 ≤ i ≤ K をみたす i それぞれについて答えを計算し、 10^9+7 で割った余りを答えてください。

制約

  • 1 ≤ K ≤ N ≤ 2000

入力

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

N K

出力

i 行目 (1 ≤ i ≤ K) に高橋君がちょうど i 回操作をする必要があるボールの並べ方の総数を 10^9+7 で割った余りを出力せよ。


入力例 1

5 3

出力例 1

3
6
1

高橋君がちょうど 1 回操作をする必要があるボールの並べ方は (青, 青, 青, 赤, 赤), (赤, 青, 青, 青, 赤), (赤, 赤, 青, 青, 青) の 3 通りです。

高橋君がちょうど 2 回操作をする必要があるボールの並べ方は (青, 青, 赤, 青, 赤), (青, 青, 赤, 赤, 青), (赤, 青, 青, 赤, 青), (赤, 青, 赤, 青, 青), (青, 赤, 青, 青, 赤), (青, 赤, 赤, 青, 青) の 6 通りです。

高橋君がちょうど 3 回操作をする必要があるボールの並べ方は (青, 赤, 青, 赤, 青) のみの 1 通りです。


入力例 2

2000 3

出力例 2

1998
3990006
327341989

並べ方の総数を 10^9+7 で割った余りを出力することに注意してください。

Score : 400 points

Problem Statement

There are K blue balls and N-K red balls. The balls of the same color cannot be distinguished. Snuke and Takahashi are playing with these balls.

First, Snuke will arrange the N balls in a row from left to right.

Then, Takahashi will collect only the K blue balls. In one move, he can collect any number of consecutive blue balls. He will collect all the blue balls in the fewest moves possible.

How many ways are there for Snuke to arrange the N balls in a row so that Takahashi will need exactly i moves to collect all the blue balls? Compute this number modulo 10^9+7 for each i such that 1 \leq i \leq K.

Constraints

  • 1 \leq K \leq N \leq 2000

Input

Input is given from Standard Input in the following format:

N K

Output

Print K lines. The i-th line (1 \leq i \leq K) should contain the number of ways to arrange the N balls so that Takahashi will need exactly i moves to collect all the blue balls, modulo 10^9+7.


Sample Input 1

5 3

Sample Output 1

3
6
1

There are three ways to arrange the balls so that Takahashi will need exactly one move: (B, B, B, R, R), (R, B, B, B, R), and (R, R, B, B, B). (R and B stands for red and blue, respectively).

There are six ways to arrange the balls so that Takahashi will need exactly two moves: (B, B, R, B, R), (B, B, R, R, B), (R, B, B, R, B), (R, B, R, B, B), (B, R, B, B, R), and (B, R, R, B, B).

There is one way to arrange the balls so that Takahashi will need exactly three moves: (B, R, B, R, B).


Sample Input 2

2000 3

Sample Output 2

1998
3990006
327341989

Be sure to print the numbers of arrangements modulo 10^9+7.