← 返回题目列表

AtCoder · ttpc2015_j

J. 指点

中文机器翻译题面 查看原题

問題文

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后的余数。