一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

我们发现：如果找到图的一条生成树那么有的状态展开

而这张图是n阶完全图那么根据cayley公式这个n阶完全图的生成树个数是

这个证明就是Prufer序列

什么是Prufer序列？

这是一种完美的树hash。

一个长n-2的prufer序列完美对应一棵树

所以n阶完全图的生成树个数是

什么是prufer序列

我们先把度数为1且编号最小的节点删掉，显然先一次删掉2,3,4，即图中的绿色节点，并在Purfer编码中加入其与父节点的连边。所以在删掉2,3,4后，Purfer编码为[1,1,1]。此时1号节点度数为1，且编号最小，所以应删去1号节点，接着删去6,7,8,号节点，即图中的红色节点。在删掉1,6,7,8,后，Purfer编码变为[1,1,1,5,5,5,5]。此时只剩下两个点，编码结束。

可以看出，Purfer编码唯一对应一棵树的形态。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef int INT;#define int long longconst int mod=9999991;int Quick_Pow(int x,int k){	int ret=1;	while(k){		if(k&1){			ret=ret*x%mod;		}		x=x*x%mod;		k/=2;	}	return ret;}int n;INT main(){	freopen("monkey.in","r",stdin);	freopen("monkey.out","w",stdout);	cin>>n;	int ans=Quick_Pow(n,n-2);	for(int i=1;i<=n-1;++i){		ans=ans*i%mod;	}	cout<