問題文
N有人,并且每个人都指向除了自己以外的某个人。1在这种情况下,没有人是无人指向的。
当汇报每个人沿被指的手指追溯多少次才第一次回到自己时,其最大值是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
3 3
出力例1
2
每个人都有1、2、3当1→2→3→1这种指向方式,以及1→3→2→1这种指向方式,共两种。
入力例2
4 2
出力例2
3
每个人都有1、2、3、4当1→2→1、3→4→3这种指向方式,以及1→3→1、2→4→2这种指向方式,以及1→4→1、2→3→2这种指向方式共有三种。
入力例3
3 2
出力例3
0
也有可能不存在满足条件的指向方式。
入力例4
1000 1000
出力例4
756641425
答案可能非常大,1,000,000,007后的余数。