← 返回题目列表

Codeforces · 288/B

B. 企鹅波罗和房子

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

小企鹅波罗爱他的家乡。该村有 n 栋房屋,用 1 到 n 的整数索引。每个房子都有一个包含整数的牌匾,第 i 个房子有一个包含整数 pi (1 ≤ pi ≤ n) 的牌匾。

小企鹅波罗喜欢在这个村庄里散步。步行看起来就是这样。首先,他站在 x 号门牌旁。然后他去x房子牌匾上写着门牌号的房子(即去px房子),然后他去到px房子牌匾上写着门牌号的房子(即去ppx房子),以此类推。

我们知道:

1. 当企鹅从任何索引为 1 到 k(含)的房子开始行走时,他可以走到 1 号房子。
2. 当企鹅从索引为 k + 1 到 n(含)的任何房子开始行走时,他绝对不能走到 1 号房子。
3. 当企鹅从 1 号房子开始行走时,经过非零次数的从一栋房子到另一栋房子的步行后,他可以回到 1 号房子。

您需要找出在房屋牌匾上书写数字的方法数,以满足上述三个条件。打印该数字除以 1000000007 (109 + 7) 后的余数。

输入

单行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 1000, 1 ≤ k ≤ min(8, n)) — 语句中的房屋数量和数字 k。

输出

在一行中打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

5 2

输出 #1

54

输入 #2

7 4

输出 #2

1728