小企鹅波罗爱他的家乡。该村有 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