来源：题解

比较不错的博客：http://www.cnblogs.com/dirge/p/5503289.html

最后生成一颗无根树，有n^(n-2)种情况，打架的顺序有(n-1)!种

#include
     
      using namespace std;const int mod=9999991;int n;long long ans=1;int main(){    scanf("%d",&n);    for(int i=1;i<=n-2;i++)ans=(ans*n)%mod;    for(int i=1;i<=n-1;i++)ans=(ans*i)%mod;    printf("%lld\n",ans);}
     

最后生成一颗有根树，每个点做根有n^(n-2)种情况，共n^(n-1)种

#include
     
      #define ll long longusing namespace std;const int mod=1e9+9;ll n;inline ll qpow(ll a,ll b){    ll base=a,ans=1;    while(b){        if(b&1)ans=(ans*base)%mod;        base=(base*base)%mod;        b>>=1;    }    return ans%mod;}int main(){
   int T;    scanf("%d",&T);    for(int pp=1;pp<=T;pp++){        scanf("%d",&n);        printf("%lld\n",qpow(n,n-1));    }}