RT

#include <bits/stdc++.h>
using namespace std;
const int maxm=400005;
const int maxn=2000005;
const int dd=104857601;
int n,cnt;
short mu[maxn];
int sum2[maxn],sum3[maxn],prime[maxm];
bool p[maxn];
inline int read() {
	int ret=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-')f=-f;
		ch=getchar();
	}
	while(isdigit(ch)) {
		ret=ret*10+ch-'0';
		ch=getchar();
	}
	return ret*f;
}
int qpow(int x,int p) {
	int ans=1;
	if(p<0)	p+=dd-1;
	while(p) {
		if(p&1)	ans=1ll*ans*x%dd;
		p>>=1;
		x=1ll*x*x%dd;
	}
	return ans;
}
int inv(int x) {
	return qpow(x,dd-2);
}
void prework() {
	n=read();
	sum2[0]=sum2[1]=sum3[0]=sum3[1]=1;
	mu[1]=1;	prime[0]=0;
	for(int k=2;k<=n;k++)
	{
		if(!p[k])
		{
			prime[++cnt]=k;
			mu[k]=-1;
		}
		for(int j=1;j<=cnt&&k<=n/prime[j];j++)
		{
			p[k*prime[j]]=1;
			if(k%prime[j]==0)
			{
				mu[k*prime[j]]=0;
				break;
			}
			mu[k*prime[j]]=-mu[k];
		}
		sum3[k]=1ll*sum3[k-1]*qpow(k,mu[k])%dd;
		mu[k]+=mu[k-1];
		sum2[k]=1ll*sum2[k-1]*k%dd;
	}
}
int calc(int n) {
	long long ans=1;
	for(int l=1,r; l<=n; l=r+1) {
		r=n/(n/l);
		ans=ans*qpow(sum2[n/l],1ll*(mu[r]-mu[l-1])*(n/l)%(dd-1))%dd;
		ans=ans*qpow(1ll*sum3[r]*inv(sum3[l-1])%dd,1ll*(n/l)*(n/l)%(dd-1))%dd;
//		cout<<sum2[n/l]<<" "<<s<<" "<<sum3[r]*inv(sum3[l-1])%dd<<" "<<p<<endl;
	}
//	cout<<n<<" "<<ans<<endl;
	return ans;
}
void solve() {
	long long ans=1;
	for(int l=1,r; l<=n; l=r+1) {
		r=n/(n/l);
		ans=ans*qpow(calc(n/l),r-l+1)%dd;
	}
	printf("%lld\n",ans*ans%dd);
}
signed main() {
	prework();
	solve();
	return 0;
}