rt，$30 \%$ 后的数据全部输出0

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>

#define ll long long
#define _it set<node>::iterator
#define MAX 0x7fffffff
#define db double
#define init inline int
#define INF 0X3fffffff
#define ts cout<<"done\n";
#define N 1000005

using namespace std;

inline long long read(){
	ll f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*f;
}

const int mod = 104857601;

ll n,m;

ll qpow(ll x,ll y){
	if(!y) return 1;
	if(y==1) return x;
	ll res=qpow(x,y/2);
	if(y&1) return (((res*res)%mod)*x)%mod;
	return (res*res)%mod;
}

vector<int>p;
short u[N],v[N];

void prime(){
	v[1]=1;u[1]=1;
	for(int i=2;i<=N;i++){
		if(v[i]==0) {p.push_back(i);u[i]=-1;}
		int cnt=p.size();
		for(int j=0;j<cnt&&i*p[j]<=N;j++){
			v[i*p[j]]=1;
			if(!(i%p[j])) {u[i*p[j]]=0;break;}
			else u[i*p[j]]=-u[i];
		}
	}
	for(int i=1;i<=N;i++) u[i]=u[i-1]+u[i];
}

ll cale(ll n){
	ll r=0,res=0;
	for(int l=1;l<=n;l=r+1){
		r=n/(n/l);
		res+=1ll*(n/l)%(mod-1)*(n/l)%(mod-1)*(u[r]-u[l-1]+mod-1)%(mod-1);
		res=(res+mod-1)%(mod-1);
	}
	return res%(mod-1);
}

long long jc(ll x){
	ll res=1;
	for(ll i=2;i<=x;i++) res=1ll*res*i,res%=mod;
	return res;
}

int main(){
	n=read();
	prime();
//	cout<<"done\n";
	ll S=jc(n);
	ll ans=1;
	for(ll d=1;d<=n;d++){
		int res=cale(n/d);
		ans=(1ll*ans*qpow(d*d,res))%mod;
		//	cout<<res<<" "<<ans<<"\n";
	}
	ans=qpow(ans,mod-2);
	cout<<(1ll*ans*qpow(S,2*n)%mod)%mod;
	return 0;
}