Description
saruka有一座大大的城堡！城堡里面有n个房间，每个房间上面都写着一个数字p[i]。有一天，saruka邀请他的小伙伴LYL和 MagHSK来城堡里玩耍（为什么没有妹子），他们约定，如果某一个人当前站在i号房间里，那么下一步他就要去p[i]号房间，在下一步就要去 p[p[i]]号房间。
为了增加趣味性，saruka决定重新书写一下每个房间的p[i]，以满足：
<1>如果从编号为1-k的某个房间走，按照规则走，必须能走回1号房间。特别的，如果从1号房间开始走，也要走回1号房间。（至少走一步，如果p[1] = 1，从1走到1也算合法）
<2>如果从编号大于k的房间开始，按照规则走，一定不能走到1号房间。
saruka想知道，一共有多少书写p[i]的方案可以满足要求？
Input
共一行两个数字n，k，含义如题。
Output
一个数字，表示合法的方案数。答案对10 ^ 9 + 7取模。
Sample Input
5 2
7 4
Sample Output
54
1728
Hint
1 <= n <= 10 ^ 18
1 <= k <= min(8，n)
题解
很显然这道题我们要分治考虑，即分为$[1,k]$和$[k+1,n]$两个区间的点来计算。
首先我们很容易的知道后面这个区间的个数是${(n-k)}^{n-k}$，因为后面的点不能与$[1,k]$的点连，并且可以随便连，不用管是否连通。
那么我们现在考虑前面的$k$个点。我们想：首先这个图是一个典型的基环内向树，既然所有的点都能到达$1$号点，那么这个$1$号点肯定在基环上，并且整个图都是连通的。
我们来考虑这个问题：怎样构成这个图呢？
我们先假设只有$n-1$条边，那么使图要连通的话，显然构成了一棵树且根节点为$1$；因为边是有向的，显然所有边的方向是从儿子节点到父节点。
现在我们加上忽略的这条边，显然我从$1$号根节点连向任意一个节点都是可以的（包括根节点）。
我们拓展到一般的情况如果$1$号点不一定是根节点：那么我们只要把根节点连向$1$号点的位置就可以了。
我们得出这样一个结论：只要构成了一棵树，我都有方法使它满足条件，并且无论根节点是什么。并且我们能够得到，一个无向树确定了根节点，我都有办法确定方向使它们指向根。
带编号的点的无根生成树我们想到了$Cayley$公式，不知道的可以戳我之前写的一篇博客：->戳我<-
我们可以得到$n^{n-2}$棵无根树，并且我所有的点都可以确立为根，那么在每种形态下，我又有了$n$个版本。
那么前一部分的方案数就是$k^{k-1}$。
根据乘法原理：最终答案就是$k^{k-1}*{(n-k)}^{n-k}$。
//It is made by Awson on 2017.10.12
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x)*(x))
using namespace std;
const LL MOD = 1e9+; LL n, k; LL quick_pow(LL a, LL b) {
LL sum = ;
a %= MOD;
while (b) {
if (b&) sum = sum*a%MOD;
b >>= ;
a = a*a%MOD;
}
return sum;
}
void work() {
scanf("%lld%lld", &n, &k);
LL ans1 = quick_pow(k, k-);
LL ans2 = quick_pow(n-k, n-k);
printf("%lld\n", ans1*ans2%MOD);
}
int main() {
work();
return ;
}