题目链接：
E - Tunnel Network
题目大意：
给定编号1-n的点，和给定编号1-S 的联通图，刚开始1号联通图只有 1个顶点，就是编号为1的顶点，2号联通图也只有1个顶点，编号为2的顶点，同理 3，4，5知道s；
剩下的顶点还有 s+1,s+2,s+3,….到n；
这些点你可以随机分配，以连边的方式加入到S个联通图里，
现在问。。。最后由N个点构成的森林。。种类，方案数有多少？
凯莱定理讲解：http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html
https://blog.csdn.net/qq_31664927/article/details/51705923
这两个配着理解就好了。
对于这个题，我们转化为purfer 数列的时候，因为那一层前n-s-1个我们是可以从1-n里面选的，但是n-s个就必须是1-中的了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int mod = 1e9+;
const int maxn = 3e4+;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,s;
scanf("%lld %lld",&n,&s);
ll ans=s;
for(int i=;i<=n-s-;i++){
ans=(ans*n)%mod;
}
printf("%lld\n",n==s?1ll:ans);
}
return ;
}