题目背景

本题满分 $70$。

题目描述

Ivan 在今年的巧克力节工作时，老板给了他 $n$ 个互不相同的巧克力糖果，让他用这些糖果准备 $k$ 个巧克力盒。Ivan 想知道一共有多少种不同的摆放方式（之后再从中选最好的）。

糖果的摆放必须满足：

• 每个盒子至少包含 $1$ 颗糖；
• 每颗糖恰好放入 $1$ 个盒子；
• 盒子彼此完全相同：交换两个盒子的内容不算产生新方案。我们只关心每个盒子里有哪些糖，以及它们在盒子里的排列顺序；
• 每个盒子中，最大的那颗糖必须放在该盒子的第一个位置。（可以认为任意一组糖的最大值都能唯一确定。）

问共有多少种摆放方式？答案可能很大，请输出它对 $10^9+7$ 取模的结果。

输入格式

一行包含两个自然数 $n, k$（$1 \le k \le n \le 5000$），表示糖果数与盒子数。

输出格式

输出一行，包含一个整数，表示方案数 $\bmod\ (10^9+7)$ 的值。

3 1

2

3 2

3

4 2

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]\}$。

【子任务】

子任务	分值	限制
$1$	$8$	$k = 1$
$2$	$19$	$k = 2$
$3$	$14$	$n \le 10$
$4$	$29$	无额外限制