如果我们把选出子图看成选出边，进而看成对边黑白染色，那么就是上一题的弱化版了，直接复制过来然后令(m=2)即可
不过直接交上去会T，于是加了几发大力优化
不知为何华丽的被小号抢了rank2
//minamoto
#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
using namespace std;
const int N=105,P=997;
int ans,n,m,fac[N],inv[N],rec[N],Gcd[N][N];
int GCD(int i,int j){
if(Gcd[i][j])return Gcd[i][j];
if(!i)return Gcd[i][j]=j;if(!j)return Gcd[i][j]=i;
return Gcd[i][j]=GCD(j,i%j);
}
int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=x*x%P)if(y&1)res=res*x%P;
return res;
}
void calc(int x){
int sum=0,mul=1,now=1;
fp(i,1,x)sum+=rec[i]/2;
fp(i,1,x)fp(j,i+1,x)sum+=Gcd[rec[i]][rec[j]];
fp(i,1,x)(mul*=rec[i])%=P;
fp(i,2,x){
if(rec[i]!=rec[i-1])(mul*=fac[now])%=P,now=0;
++now;
}(mul*=fac[now])%=P,mul=fac[n]*ksm(mul,P-2)%P;
(ans+=mul*ksm(m,sum)%P)%=P;
}
void dfs(int k,int x,int s){
if(!x)calc(k-1);if(x<s)return;
fp(i,s,x)rec[k]=i,dfs(k+1,x-i,i);
}
void init(){
fac[0]=1;fp(i,1,n)fac[i]=fac[i-1]*i%P;
fp(i,1,n)Gcd[i][0]=Gcd[0][i]=i;
fp(i,1,n)fp(j,1,n)GCD(i,j);
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d",&n),m=2,init();
dfs(1,n,1);(ans*=ksm(fac[n],P-2))%=P;
printf("%d
",ans);return 0;
}