巧克力节

题目描述:

动物城为了庆祝兔警官朱迪和狐狸尼克破获神秘案件，特意举办了盛大的巧克力节。在巧克力节上，朱迪给尼克 $n$个编号为 $1 \le i \le n$的巧克力糖果，让他将这些糖果放入 $k$ 个巧克力盒中。朱迪想知道一共有多少种不同的摆放方式，然后再从中选出摆放样式最好的那一个，送给今天来参加考试的你。

巧克力糖果的摆放必须满足：

• 每个盒子至少包含$1$颗巧克力糖果。
• 每颗巧克力糖果恰好放入$1$个巧克力盒子中。
• 巧克力盒子彼此完全相同：交换两个巧克力盒子的内容不算产生新方案。我们只关心每个盒子里有哪些巧克力糖果，以及它们在盒子里的排列顺序。
• 每个巧克力盒子中，编号最大的那颗巧克力糖果必须放在该盒子的第一个位置。

朱迪很想知道一共有多少种不同的摆放方式？答案可能很大，请输出它对（ $10^9 + 7$ ）取模的结果。

输入格式:

输入共一行包含两个整数 $n,k$，分别表示巧克力糖果数与巧克力盒子数。

输出格式:

输出共一行一个整数，表示方案数对（ $10^9 + 7$ ）取模的结果

数据范围:

对于100%的数据：$1 \le k \le n \le 10,000 $

测试点编号	特殊限制
1~2	$k=1$
3~4	$k=2$
5~8	$ 1 \le  k \le n \le 10$
9~16	$ 1 \le k \le n \le  5000$
17~20	无特殊限制

样例输入:

(双击复制)

样例1;
3 1

样例2：
3 2

样例3：
4 2

样例输出:

(双击复制)

样例1;
2

样例2：
3

样例3：
11

提示:

【样例1解释】

尼克将糖果按从小到大编号依次为$1,2,3$ 。只有$1$个盒子，因此全都放在同一个盒中。编号最大的糖果$3$必须在第一位，其余两颗可以任意排列。合法的摆放方案为$3,1,2$和$3.2.1$ ，共$2$种摆放方案。

【样例2解释】

尼克将糖果按从小到大编号依次为 $1,2,3$。分到$2$个相同的盒子中，共有$3$种摆放方案：

第一种摆放方案 ${1},{3,2}$。

第二种摆放方案  ${2},{3,1}$。

第三种摆放方案  ${3},{2,1}$。

时间限制: 1000ms
空间限制: 256MB

---

来源: 26年比赛初中组t4