Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

ll ans = 0;

#define MAXN 65

ll fac[MAXN];

const ll p = 997;

const ll c = 2;

#define MOD 1000

ll inver[MOD];

inline ll power(ll a,ll b)

{

	register ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % p;

		a = a * a % p;

		b = b >> 1;

	}

	return res;

}

ll cnt[MAXN];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

ll l[MAXN];

ll pow2[MOD];

ll g[MAXN][MAXN];

inline ll calc(ll x)

{

	register ll m = 0;

	for(register int i = 1;i <= x;++i)m = (m + l[i] / 2) % (p - 1);

	for(register int i = 1;i < x;++i)for(register int j = i + 1;j <= x;++j)m = (m + g[l[i]][l[j]]) % (p - 1);

	register ll s = 1;

	for(register int i = 1;i <= x;++i)s = s * l[i] % p;

	s %= p;

	for(register int i = 1;i <= n;++i)s = s * fac[cnt[i]] % p;

	return inver[s] * pow2[m] % p;

}

void dfs(ll cur,ll rem,ll low)

{

	if(rem == 0)

	{

		ans = (ans + calc(cur - 1)) % p;

		return;

	}

	for(register ll i = low;i <= rem;++i)

	{

		++cnt[i];l[cur] = i;

		dfs(cur + 1,rem - i,i);

		--cnt[i];

	}

	return;

}

int main()

{

	scanf("%lld",&n);

	inver[1] = 1;for(int i = 2;i < MOD;++i)inver[i] = (p - p / i) * inver[p % i] % p;

	fac[0] = 1;for(register int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % p;

	pow2[0] = 1;for(int i = 1;i < MOD;++i)pow2[i] = pow2[i - 1] * 2 % p;

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)g[i][j] = gcd(i,j);

	dfs(1,n,1);

	cout << ans << endl;

	return 0;

}