90分代码：

#include<bits/stdc++.h>
#define eps 1e-10
using namespace std;
typedef long long LL;
template<typename T>void qw(T x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48); 
}   
__int128 a[110][110];//基尔霍夫矩阵
void add(int x,int y){a[x][x]+=1;a[y][y]+=1;a[x][y]-=1;a[y][x]-=1;}
/*
任意图的生成树个数:
生成树计数行列式a[i][i] = Di，Di为i的度数;
a[i][j] = -k，k为i和j之间的边数。
任去一行一列之后的行列式即为答案。
（往往是去掉第n行第n列） 
*/
int n,m;
void gauss()
{
	__int128 ans=1;
	int r=1;
    for(int c=1;c<=n;c++)
	{
        for(int i=r+1;i<=n;i++)
		{
            while(a[i][c])
			{
                __int128 bs=a[r][c]/a[i][c];
                for(int j=1;j<=n;j++)a[r][j]=a[r][j]-a[i][j]*bs;
                swap(a[r],a[i]);
                ans*=-1;
                //每次交换两行，将答案取相反数
            }
        }
        if(a[r][c]!=0)r++;
	}
    for(int i=1;i<=n;i++)ans*=a[i][i];
    qw(ans);
}
int main() 
{
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++) 
    {
        int x=i,y=n+1;
        add(x,y);
    }
    for(int i=1;i<=n;i++) 
    {
        int x=i,y=i+1;if(y==n+1)y=1;
        add(x,y);
    }
    gauss();
    return 0;
}