#include<bits/extc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using namespace __gnu_pbds;
const int N=1e6+5,mod=998244353,I2=(mod+1)>>1;
int U,pw[N],pr[N/10],mu[N],MU[N],tot,sq;bool v[N];LL n;
struct node{int f,g,h;}a[N],b[N];
inline int md(int x){return x>=mod?x-mod:x;}
inline void ad(int &x,int y){x=md(x+y);}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
inline int TO(int x){return x<=sq?x:tot+1-(n/x);}
inline void init(int M)
{
	for(int i=2;i<=M;i++)
	{
		if(!v[i]) pr[++pr[0]]=i,mu[i]=-1;
		for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
		{
			v[i*pr[j]]=1;if(i%pr[j]==0) break;
			mu[i*pr[j]]=-mu[i];
		}
	}mu[1]=1;
	for(int i=pw[0]=1;i<=M;i++) pw[i]=md(pw[i-1]<<1);a[1].g=1;
	for(int i=2;i<=M;i++)
	{
		a[i].f=md(a[i].f+pw[i/2-1]-1);
		a[i].g=md(a[i].g+mod-(2ll*a[i].f+pw[i-1]-2*mu[i])%mod);
		a[i].h=md(a[i].h+mod-(2ll*a[i].f+pw[i-1]-mu[i])%mod);
		int F=(3ll*(a[i].f+pw[i-2]))%mod;
		for(int j=i;j<=M;j+=i)
			a[j].g=(a[j].g+2ll*(mu[j/i]+mod)*F)%mod,
			a[j].h=(a[j].h+1ll*(mu[j/i]+mod)*F)%mod;
		for(int j=i+i;j<=M;j+=i)
			a[j].f=(a[j].f+a[i].h+1ll*a[i].g*(pw[j/(i<<1)-1]-1))%mod;
	}
	for(int i=1;i<=M;i++) ad(a[i].f,a[i-1].f),ad(a[i].g,a[i-1].g),ad(a[i].h,a[i-1].h);
	for(int i=2;i<=M;i++) mu[i]+=mu[i-1];
	for(int i=1;i<=M;i++) mu[i]=md(mu[i]+mod);
}
int Mu(LL n)
{
	if(n<=U) return mu[n];int w=TO(n);
	if(MU[w]!=-1) return MU[w];int ans=0;
	for(LL i=2,j;i<=n;i=j+1) j=n/(n/i),ans=(ans+(j-i+1)%mod*Mu(n/i))%mod;
	return MU[w]=md(mod+1-ans);
}
int S(LL n)
{
	if(n<=1) return 0;LL k=n>>1;
	if(n&1) return ((pw[TO(n/2)]-k-1)%mod+mod)*2%mod;
	int t=1ll*pw[TO(n/2)]*(1+I2)%mod,r=mod-(k+1)%mod;
	return (t+2ll*r+1)%mod;
}
node sol(LL n)
{
	if(n<=U) return a[n];int w=TO(n);
	if(b[w].f!=-1) return b[w];int F=0,G=0,H=0;
	for(LL i=2,j;i<=n;i=j+1)
	{
		j=n/(n/i);
		
	}
	return a[w]={F,G,H};
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
	for(LL i=1,j;i<=n;i=j+1) j=n/(n/i),tot++;
	for(int i=1;i<=tot;i++) MU[i]=-1,b[i]={-1,-1,-1};
	init(U=n);sq=sqrtl(n);pw[0]=1;
	for(LL i=1,j,c=tot;i<=n;i=j+1,c--) j=n/(n/i),pw[c]=ksm(2,(n/i)%(mod-1));
	// for(int i=1;i<n;i++)
	// {
	// 	int s=0;
	// 	for(int j=1;j<=i;j++)
	// 	{
	// 		s=(s+1ll*(mu[j]+mod)*F(i/j))%mod;
	// 	}
	// 	a[i].h=(-2ll*a[i].f-ksm(2,i)+1+s)%mod;
	// 	a[i].h=(mod+a[i].h)%mod;
	// 	a[i].g=(-2ll*a[i].f-ksm(2,i)+1+2ll*s)%mod;
	// 	a[i].g=(mod+a[i].g)%mod;
	// 	for(int j=2;j<=i+1;j++)
	// 	{
	// 		f[i+1]=(f[i+1]+1ll*g[(i+1)/j]*(ksm(2,j/2-1)-1)+h[(i+1)/j])%mod;
	// 	}
	// }
	cout<<(sol(n).f+ksm(2,(n-1)%(mod-1)))%mod;
	return 0;
}