题意：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1805
题解：
根据cayley公式，无向图的每一个生成树就对应一个序列（共有n^（n-2）个），具体定义见 http://www.matrix67.com/blog/archives/682
根据定义，这个n-2项中没有出现的点为叶子结点，所以我们先求C（n,m）表示那些点为叶子，再乘上序列的数量
S（n,m） = C(m,0)m^n - C(m,1)(m-1)^n + C(m,2)(m-2)^n - .... (容斥定理)
#include<bits\stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1000100;
const LL Mod = 1e9 + 7;
LL jc[maxn];
LL ny[maxn]; LL ksm(LL x,LL y)
{
LL ans = 1;
while(y){
if(y&1){
ans = ans*x%Mod;
}
y >>= 1;
x = x*x%Mod; }
return ans;
} LL getc(LL n,LL m)
{
if( m == 0 || n == m)
return 1;
return (jc[n]*ny[m]%Mod)*ny[n-m]%Mod;
} void pre(int n)
{
jc[1] = ny[1] = 1; for(int i = 2; i <= n; i++){
jc[i] = i * jc[i-1] % Mod;
ny[i] = (Mod - Mod/i) * ny[Mod%i] % Mod;
}
for(int i = 2; i <= n; i++){
ny[i] = ny[i] * ny[i-1] % Mod;
} } int main()
{
LL ans = 0;
LL n,m;
cin>>n>>m;
pre(n); LL c = getc(n,m);
LL k = n - m;
while(k){
if((k&1) == ((n-m)&1))
ans = (ans+ getc(n-m,k) * ksm(k,n-2) % Mod )% Mod;
else
ans = (Mod + ans - getc(n-m,k) * ksm(k,n-2) % Mod)% Mod; k--;
}
if(n == 2 && m == 2)
cout<<1<<endl;
else
cout<<c*ans%Mod<<endl;
return 0;
}