#include<bits/stdc++.h>
using namespace std;
int prim[1000001],cnt=0,mu[1000001];
bool vis[1000001];
long long tmp[1000001];
void in(__int128&a) {
	long long b;
	cin>>b;
	a=b;
}
void out(__int128 a) {
	long long b=a;
	cout<<b;
}
void init(__int128 n) {
    mu[1]=1;
	for(__int128 i=2;i<=n;i++) {
		if(!vis[i])	cnt++,prim[cnt]=i,mu[i]=-1;
		for(__int128 j=1;j<=cnt&&prim[j]*i<=n;j++) {
			vis[i*prim[j]]=1;
			if(!(i%prim[j])) {
				mu[i*prim[j]]=0;
				break;
			}
			mu[i*prim[j]]=-mu[i];
		}
	}
	for(__int128 i=1;i<=n;i++)
		mu[i]+=mu[i-1];
    tmp[1]=1;
    tmp[0]=1;
    for(__int128 i=2;i<=n;i++)
    	tmp[i]=i*tmp[i-1],tmp[i]%=104857601;
}
__int128 qpow(__int128 w,__int128 p) {
	if(p==0)
		return 1;
	__int128 tp=qpow(w,p/2);
	return tp%104857601*tp%104857601*(p%2?w:1)%104857601;
}
__int128 sol(__int128 n) {
	__int128 ans=0,l=1;
	while(l<=n) {
		__int128 r=n/(n/l);
		ans+=(mu[r]-mu[l-1])%104857600*(n/l)%104857600*(n/l)%104857600;
		ans%=104857600;
		l=r+1;
	} 
	return ans;
}
__int128 does(__int128 n) {
	__int128 l=1,ans=1;
	while(l<=n) {
		__int128 r=n/(n/l);
		ans*=qpow(tmp[r]*qpow(tmp[l-1],104857599)%104857601,sol(n/l));
		ans%=104857601;
		l=r+1;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init(1000000);
	__int128 n;
	in(n);
	out((qpow(tmp[n],2*n)*qpow((does(n)),104857598)%104857601+104857601)%104857601);
}