前言

https://www.luogu.com.cn/problem/P4430
树的尽头便是数论吗（QAQ）

思路

前置技能:
Cayley定理：
不同的n节点带标号生成无根树的数量为 n n − 2 n^{n-2} nn−2

又因为题中不考虑前后顺序(也就是排列)
对于生成的树有(n-1)条边,所以 这题的公式如下:

( n − 1 ) ! ∗ n n − 2   m o d   9999991 (n-1) ! * n^{n-2} \bmod 9999991 (n−1)!∗nn−2mod9999991

CODE

#include 
using namespace std;
using ll = long long;
ll ans = 1;
int n;

void solve()
{
    cin>>n;
    for(int i=1;i