P14778 [COCI 2025/2026 #3] 节日 / Festival

本题满分 $70$。

Ivan 在今年的巧克力节工作时，老板给了他 $n$ 个**互不相同**的巧克力糖果，让他用这些糖果准备 $k$ 个巧克力盒。Ivan 想知道一共有多少种不同的摆放方式（之后再从中选最好的）。 糖果的摆放必须满足： - 每个盒子至少包含 $1$ 颗糖； - 每颗糖恰好放入 $1$ 个盒子； - 盒子彼此**完全相同**：交换两个盒子的内容不算产生新方案。我们只关心每个盒子里有哪些糖，以及它们在盒子里的排列顺序； - 每个盒子中，**最大**的那颗糖必须放在该盒子的第一个位置。（可以认为任意一组糖的最大值都能唯一确定。） 问共有多少种摆放方式？答案可能很大，请输出它对 $10^9+7$ 取模的结果。

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

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

#### 【样例解释】 样例 #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$ | 无额外限制 |