You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述 小 G 家有一座城堡。城堡里面有 n 个房间，每个房间上都写着一个数字 pi。 小 G 拉着几个小伙伴在城堡里面玩耍，他们约定，如果某个人当前站在 i 房间里面，下一步这个人就会去 pi 房间，再下一步这个人去 ppi。 为了增加趣味性，小 G 想重新书写每个房间的 pi，以满足： • 如果从编号 1 到 k 中的某个房间开始，按照规则走，必须能够走到 1 号房间。 特别地，如果从 1 号房间开始走，也要能够走回 1 号房间（至少走一步，如果 p1 = 1，从 1 走到 1 也算合法）。 • 如果从编号大于 k 的某个房间开始，按照规则走，一定不能走到 1 号房间。 小 G 想知道，有多少种书写 pi 的方案，可以满足要求。 输入格式 输入文件一行两个数字 n,k，含义如题。 输出格式 输出文件一个数字，表示合法的方案数。答案对 109 +7 取模。 样例输入1 5 2 样例输出1 54 样例输入2 7 4 样例输出2 1728 数据范围 对于 40% 的数据，1 ≤ n ≤ 8 对于 70% 的数据，1 ≤ n ≤ 105 对于 100% 的数据， 。