#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=1e7+10,mod=998244353; int n; int vis[maxn]; vector<int>p; void init(){ int n=4e4;vis[1]=1; up(i,2,n){ if(!vis[i])p.eb(i); for(int j:p){ if(i*j>n)break; vis[i*j]=1;if(!(i%j))break; } } } const int tab[]={0,664579,606028,587252,575795,567480,560981,555949,551318,547572,544501,541854,538339,536539,534012,532197,530062,528625,527302,525088,523464,522689,520914,520033,518971,517774,516542,515524,514685,513594,512662,512196,510685,510269,509130,508921,507762,507117,506968,505837,505116,504387,503766,503571,502505,502483,501510,501170,500706,499944,499499,498385,498435,498011,497683,496975,496794,496136,495889,495369,495159,494741,493944,493841,493221,492945,492775,492149,491848,491580,491184,490974,490143,490122,489817,489194,489038,488760,488497,488777,487926,488008,487315,486902,487006,486556,485874,486048,485473,485051,484803,485342,485026,483850,483991,484047,483845,483482,482782,483129,482825}; int work(int l,int r){ up(i,1,r-l+1)vis[i]=0; if(l==1)vis[1]=1; for(int x:p){ for(int i=max((l+x-1)/x,2)*x;i<=r;i+=x) vis[i-l+1]=1; } int res=0; up(i,1,r-l+1)if(!vis[i])res++; return res; } int calc(int n){ int res=0; for(int i=1,j=1;i<=n;i+=1e7,j++){ if(n-i+1>=1e7)res+=tab[j]; else {res+=work(i,n);break;} } return res; } void slv(){ n=read();init(); int c=0; for(int i=2;i*i<=n;++i)if(!vis[i])for(ll j=1;j<=n;j*=i)c+=j>n/2; int res=1;up(i,1,c)res=res*2%mod; // for(int i=1;i<=1e9;i+=1e7) // cout<<work(i,i+1e7-1)<<",";cout<<endl; c=calc(n)-calc(n/2)+1; up(i,1,c)res=res*1ll*i%mod; cout<<res; } int main(){ //freopen("beautiful.in","r",stdin),freopen("beautiful.out","w",stdout); slv(); return 0; }