101323: [AtCoder]ABC132 D - Blue and Red Balls

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

### 题目描述 有 $K$ 个蓝球和 $N-K$ 个红球。同一颜色的球是完全相同的。Snuke 和 Takahashi 在玩这些球。 首先,Snuke 将把 $N$ 个球从左到右排成一排。 然后,Takahashi 将收走 $K$ 个蓝球。在一次操作中,他可以收走连续的一个区间的蓝球。他将以最少的操作数收走所有蓝球。 Snuke 有多少种排列这 $N$ 个球的方法,使得 Takahashi 至少操作 $i$ 次才能收走所有的 $K$ 个蓝球?对于每个 $i$($1\le i\le K$)计算排列数对 $10^9+7$ 取模的结果。 ------------ ### 输入格式 从标准输入读取数据,输入格式如下: $N\ K$ ------------ ### 输出格式 输出 $K$ 行。第 $i$ 行($1\le i\le K$)表示有多少种排列这 $N$ 个球的方法,使得 Takahashi 至少操作 $i$ 次才能收走所有的 $K$ 个蓝球,对 $10^9+7$ 取模。 ------------ ### 说明/提示 #### 样例解释 1 有三种方法来排列球,使得 Takahashi 至少操作 $1$ 次:$(B, B, B, R, R)$,$(R, B, B, B, R)$ 和 $(R, R, B, B, B)$。($R$ 和 $B$ 分别代表红色和蓝色)。 有六种方法来排列球,使得 Takahashi 至少操作 $2$ 次:$(B, B, R, B, R)$,$(B, B, R, R, B)$,$(R, B, B, R, B)$,$(R, B, B, R, B)$,$(B, R, B, B, R)$,和 $(B, R, R, B, B)$。 有一种方法来排列球,使得 Takahashi 至少操作 $3$ 次:$(B, R, B, R, B)$。 #### 样例解释 2 务必输出对 $10^9+7$ 的排列数。

加入题单

上一题 下一题 算法标签: