AT_ttpc2015_j.指さし

有 $N$ 个人，每个人都指向除了自己以外的某一个人。此时，没有任何一个人是没有被别人指向的。

现在，每个人都报告：如果从自己出发，沿着被指向的关系不断前进，经过多少次才能第一次回到自己。已知这些次数的最大值为 $K$。

请你计算满足上述条件的指向方式有多少种。计数时，每个人都是有区分的。

由于指向方式的数量可能非常大，请输出对 $1,000,000,007\ (=10^9+7)$ 取模的结果。

输入从标准输入中给出，格式如下：

$N$ $K$

• 第 $1$ 行包含两个用空格分隔的整数 $N\ (2 \leq N \leq 1000)$、$K\ (1 \leq K \leq N)$。

输出满足条件的指向方式数量对 $1,000,000,007$ 取模的结果。输出末尾需换行。

部分分数

本题设有部分分数。

• 对于满足 $2 \leq N \leq 8$ 的数据集，答对可得 $10$ 分。
• 对于所有数据集都答对可再得 $140$ 分，总分为 $150$ 分。

样例解释 1

将每个人编号为 $1$、$2$、$3$ 时，有 $1 \to 2 \to 3 \to 1$ 和 $1 \to 3 \to 2 \to 1$ 这两种指向方式。

样例解释 2

将每个人编号为 $1$、$2$、$3$、$4$ 时，有 $1 \to 2 \to 1$、$3 \to 4 \to 3$，$1 \to 3 \to 1$、$2 \to 4 \to 2$，$1 \to 4 \to 1$、$2 \to 3 \to 2$ 这三种指向方式。

样例解释 3

有时不存在满足条件的指向方式。

样例解释 4

答案可能非常大，请输出对 $1,000,000,007$ 取模的结果。

由 ChatGPT 4.1 翻译