图书馆新到了 N 本书,需要摆放在书架的 N 个连续格子上。其中有 K 本是完全相同的科技类图书,另外 N-K 本是完全相同的文学类的图书。
小 A 负责先将这 N 本书从左到右摆成一行。小 B 的任务是只把 K 本科技类图书全部取走。
小 B 的一次取书操作:允许一次性取走一段连续的科技类图书(即一段全部由科技类图书组成的连续段),但不能取走文学类图书,也不能跨过文学类图书去取科技类图书。
小 B 会采用最少操作次数的方式取走所有科技类图书。显然,他所需要的操作次数,恰好等于科技类图书被文学类图书分割成的连续段数。
现在,对于每种可能的操作次数 i(i \in [1, K]),请计算:小 A 有多少种不同的摆放方式,使得小 B 恰好需要 i 次操作才能取走所有科技类图书?
答案可能会很大,请输出答案对 10^9+7 取模后的结果。
输入一行,包含两个正整数 N 和 K,用一个空格分隔。
共输出 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
当 N=5、K=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
| 测试点编号 | N | K |
|---|---|---|
| 1 | N = 1 | K = 1 |
| 2 | N = 2 | K = 2 |
| 3 \sim 6 | N \le 100 | K \le 100 |
| 7 \sim 10 | N \le 2000 | K \le 2000 |
对于 100\% 的数据,满足 1 \le K \le N \le 2000。