额…看起来是一道找规律题，实际上还是挺有门道的。
题目的题意就是，求 n 个点的点、边均有标号的生成树个数。
n 个点的无根有标号生成树个数，根据某个叫做 Cayley 的古老定理， 值是：
当然，由于边有标号，所以这里的值还要乘上一个。
问题是 Cayley 定理要如何证明。
一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造，我们发现，有且仅有 种不同的方法来构造一棵有标号无根树。
这个序列是如何构造的呢？
我们考虑递归地构造这个序列。对于当前的树，我们选其中的编号最小的叶子节点，将它的相邻点——显然是唯一的——加入序列，然后删掉这个叶子节点。
这样，我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。
由此我们可以构造出这个序列。
通过 Prufer 序列，我们无损地将一棵有标号无根树的信息压缩成了一个序列。
那么要怎么把 Prufer 序列还原为一棵有标号无根树呢？我们有一种系统的方法。
首先选择一个数，这个数既不在已有的树中，也不在当前的序列中，并且它最小。那么，我们就可以确定，这个数便是我们当前要处理的叶子节点。
然后，我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。
是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢？
假设我们当前正在处理第 i 个节点，序列中剩下 k 种数，那么已经被作为叶子节点，已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点，至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ，所以叶子节点必然不会不够。
那么完成最后一步以后叶子节点会不会有剩呢？每个节点会被连接的次数正好是它在序列中出现的次数 +1 ，这也就意味着，总度数恰好是 2n-2 ，由于每一条边都无向，所以构成的正好是一张 n-1 条边的图。
最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的，我们不妨尝试证明它无环。
我们称，一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」，那么每个点的向上连边操作会且仅会发生一次。在这种情况下，环会出现，只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。
然而，向上连边的目标，一定还在 Prufer 序列中，而可以向上连边的点，一定不在 Prufer 序列中。我们于是证明了这张图无环。
既然这张 n-1 条边的图无环，那么它一定连通。
由此，我们发现，每一棵树都能唯一对应地生成一个 Prufer 序列，并且每一个 Prufer 序列都能生成一棵树。
这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;
inline ll pw(ll A,ll X){
ll RT=1;
while(X){
if(X&1){
RT*=A;
RT%=MOD;
}
A*=A;A%=MOD;X>>=1;
}
return RT;
}
int n;
void init(){
scanf("%d",&n);
ll fac=1;
for(int i=1;i<n;++i){
fac=fac*i%MOD;
}
printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
init();
return 0;
}