根据prufer序列的结论：
一个无根树对应唯一一个 prufer 序列，一个 prufer 序列也唯一对应一个无根树.
一个点在 prufer 序列中的出现次数是 $deg_{i}$ 次.
$n$ 个点完全图的生成树个数是 $n^{(n-2)}$ 个.
code:
#include <cstdio>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const ll mod=9999991;
int main()
{
// setIO("input");
int i,j,n;
scanf("%d",&n);
ll ans=1;
for(i=1;i<=n-2;++i) ans=1ll*n*ans%mod;
for(i=n-1;i>=1;--i) ans=1ll*i*ans%mod;
printf("%lld\n",ans);
return 0;
}
原文：https://www.cnblogs.com/guangheli/p/12237585.html