哦对了，不介意我来拆个台？

https://www.luogu.com.cn/record/176050447

https://www.luogu.com.cn/article/psmn6w4w

#include<bits/stdc++.h>
#define int long long
using namespace std;

int ans, n, p = 997, b[70], jc[70], jd[70];

int gcd(int a, int b){
	return !b ? a : gcd(b, a % b);
}

int qpow(int A, int B){
	int C = 1;
	while(B){
		if(B & 1) C = C * A % p;
		A = A * A % p, B >>= 1;
	}
	return C;
}

void init(){
	jc[0] = 1;
	for(int i = 1; i < 70; i++){
		jc[i] = i * jc[i - 1] % p;
	}
	// 预处理阶乘
}

void work(int len){
	int u = 0, v = 1;
	for(int i = 1; i <= len; i++){
		u += b[i] >> 1;
		for(int j = 1; j < i; j++){
			u += gcd(b[i], b[j]);
		}
		// 计算边的等价类个数，u 即题解的 k
	}
	for(int i = 1; i <= len; i++){
		v = v * b[i] % p;
	}
	for(int i = 1, j; i <= len;){
		for(j = i; b[i] == b[j] && j <= len; j++);
		v = v * jc[j - i] % p;
		// 去除长度相等的循环带来的重复计算
		i = j;
	}
	ans = (ans + qpow(v, p - 2) * qpow(2, u) % p) % p;
}

void dfs(int now, int last, int rem){
	if(!rem){
		// DFS 枚举 n 的所有拆分
		work(now - 1);
		return;
	}
	for(int i = last; i <= rem; i++){
		b[now] = i;
		dfs(now + 1, i, rem - i);
	}
}

signed main(){
	cin >> n;
	init();
	dfs(1, 1, n);
	cout << ans;
	return 0;
}

码风是真tmd灵活，心灵跟白蚁一样联通