用什么算法代码求解使N个人互相认识的方案次数

    一开始有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，
输出方案数mod 9999991。

用c或者c++

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
 
int main()
{
   int n;
   ll ans=1;
   scanf("%d",&n);
   for(int i=1;i<n;i++)
      ans=(ans*i)%9999991;
    int a=n;
   for(int i=1;i<n-1;i++)
    ans=ans*a%9999991;
   ans=ans%9999991;
   printf("%lld",ans);
    return 0;
}