CF288B.Polo the Penguin and Houses

Little penguin Polo loves his home village. The village has n houses, indexed by integers from 1 to n. Each house has a plaque containing an integer, the i-th house has a plaque containing integer p__i (1 ≤ p__i ≤ n).

Little penguin Polo loves walking around this village. The walk looks like that. First he stands by a house number x. Then he goes to the house whose number is written on the plaque of house x (that is, to house p__x), then he goes to the house whose number is written on the plaque of house p__x (that is, to house p__p__x), and so on.

We know that:

1. When the penguin starts walking from any house indexed from 1 to k, inclusive, he can walk to house number 1.
2. When the penguin starts walking from any house indexed from k + 1 to n, inclusive, he definitely cannot walk to house number 1.
3. When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house.

You need to find the number of ways you may write the numbers on the houses' plaques so as to fulfill the three above described conditions. Print the remainder after dividing this number by 1000000007 (109 + 7).

小企鹅波洛热爱他的家乡村庄。村庄里有 $n$ 座房子，编号为 $1$ 到 $n$ 的整数。每座房子门口都有一块标牌，上面写有一个整数；第 $i$ 座房子的标牌上写的整数为 $p_i$（其中 $1 \leq p_i \leq n$）。

小企鹅波洛喜欢在村庄中散步。散步过程如下：他首先站在编号为 $x$ 的房子前；然后前往标牌上写着的编号所对应的房子（即前往编号为 $p_x$ 的房子）；接着再前往该房子标牌上所写编号对应的房子（即前往编号为 $p_{p_x}$ 的房子），依此类推。

已知以下三点：

1. 当企鹅从编号为 $1$ 至 $k$（含端点）的任意一座房子出发时，他最终都能到达编号为 $1$ 的房子；
2. 当企鹅从编号为 $k+1$ 至 $n$（含端点）的任意一座房子出发时，他一定无法到达编号为 $1$ 的房子；
3. 当企鹅从编号为 $1$ 的房子出发时，经过若干次（非零次数）从一座房子走到另一座房子后，他可以回到编号为 $1$ 的房子。

你需要计算：满足上述三个条件的标牌数字 $p_1, p_2, \dots, p_n$ 的填写方案总数。请输出该总数对 $1000000007$（即 $10^9 + 7$）取模的结果。

The single line contains two space-separated integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ min(8, n)) — the number of the houses and the number k from the statement.

单行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 1000$，$1 \leq k \leq \min(8, n)$）——分别为房屋的数量以及题目描述中的数 $k$。

In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

在一行中输出一个整数——该问题答案对 $1000000007$（即 $10^9 + 7$）取模的结果。