4162 - 取书

题目描述

图书馆新到了 N 本书,需要摆放在书架的 N 个连续格子上。其中有 K 本是完全相同的科技类图书,另外 N-K 本是完全相同的文学类的图书。

A 负责先将这 N 本书从左到右摆成一行。小 B 的任务是只把 K 本科技类图书全部取走。

B 的一次取书操作:允许一次性取走一段连续的科技类图书(即一段全部由科技类图书组成的连续段),但不能取走文学类图书,也不能跨过文学类图书去取科技类图书。

B 会采用最少操作次数的方式取走所有科技类图书。显然,他所需要的操作次数,恰好等于科技类图书被文学类图书分割成的连续段数

现在,对于每种可能的操作次数 ii \in [1, K]),请计算:小 A 有多少种不同的摆放方式,使得小 B 恰好需要 i 次操作才能取走所有科技类图书?

答案可能会很大,请输出答案对 10^9+7 取模后的结果。

输入

输入一行,包含两个正整数 NK,用一个空格分隔。

输出

共输出 K 行,第 i 行(1 \le i \le K)输出一个非负整数,表示恰好需要 i 次操作的摆放方案总数,对 10^9+7 取模后的结果。

如果对于某个 i 不存在符合要求的摆放方案,请输出 0

样例

输入

5 3

输出

3
6
1

输入

2000 3

输出

1998
3990006
327341989

输入

1020 6

输出

1015
2573025
737649543
625333077
121173643
746179291
说明

样例说明 1

N=5K=3 时(用 T 表示科技类图书,W 表示文学类图书):

  • 恰好 1 次操作(所有科技类图书连成一段):共有 3 种摆法。 TTT WW
    W TTT W
    WW TTT

  • 恰好 2 次操作(科技类图书被分成 2 段):共有 6 种摆法。
    TT W T W、TT WW T、W TT W T、W T W TT、T W TT W、T WW TT

  • 恰好 3 次操作(科技类图书被分成 3 段):只有 1 种摆法。 T W T W T

数据范围

测试点编号NK
1N = 1K = 1
2N = 2K = 2
3 \sim 6N \le 100K \le 100
7 \sim 10N \le 2000K \le 2000

对于 100\% 的数据,满足 1 \le K \le N \le 2000

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题