一开始森林里面有\(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\}\)六种不同的打架过程。

Input

一个整数N。

Output

一行，方案数\(mod 9999991\)。

Sample Input

4

Sample Output

96

Hint

50%的数据\(N<=10^3\)。 100%的数据\(N<=10^6\)。

题意：

中文题面，不解释

题解：

用矩阵树定理

先得一邻接矩阵\((1)\)

再得一度数矩阵\((2)\)

\(\{2\}-\{1\}\)得基尔霍夫矩阵\((3)\)

取前\(N-1\)行\(N-1\)列高斯消元，得\((4)\)

然后求一下行列式就是答案了：

\(N^{N-2}\)

额，好吧还需要乘一个排列，因为打架的顺序可以不同

所以答案其实是：

\(N^{N-2}(N-1)!\)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll p=9999991;

ll a,ans=1;

int main(){

    cin>>a;

    for(ll i=1;i<=a-2;++i){

        ans*=a;

        ans%=p;

    }

    for(ll i=1;i<=a-1;++i){

        ans*=i;

        ans%=p;

    }

    cout<<ans<<endl;

}