#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 3000000
#define M 400000
#define mod 998244353
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x=x+d>=mod?x+d-mod:x+d;
	return;
}
void Adder2(int &x,int d)
{
	x=x+d<0?x+d+mod:x+d;
	return;
}
long long n,tong[M+1];
int length,sn,dp[N+1],DP[N+1],zdp[N+1],zDP[N+1],pw[N+1],pw2[N+1],miu[N+1],smiu[N+1],wdp[M+1],wDP[M+1],tmiu[M+1];
bool nprime[N+1];
int get_pow(long long x)
{
	return 1ll*pw[(x-1)%N+1]*pw2[(x-1)/N]%mod;
}
int S(long long x)
{
	if (x&1) return MD2(get_pow((x>>1)+1)-(x+1)%mod);
    else return MD2(3ll*get_pow((x>>1)-1)%mod-(x+1)%mod);
}
int get(long long x)
{
	if (x<=sn) return x;
	else return length-n/x+1;
}
int main()
{
	n=read();
	while (1ll*(sn+1)*(sn+1)<=n) ++sn;
	for (long long i=1,lst;i<=n;i=lst+1) lst=n/(n/i),tong[++length]=n/i;
	reverse(tong+1,tong+length+1);
	for (int i=1;i<=N;++i) miu[i]=1;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			miu[i]=-1;
			for (int j=(i<<1);j<=N;j+=i)
			{
				miu[j]=-miu[j],nprime[j]=1;
				if ((j/i)%i==0) miu[j]=0;
			}
		}
	pw[0]=pw2[0]=1;
	for (int i=1;i<=N;++i) smiu[i]=MD2(smiu[i-1]+miu[i]),pw[i]=2ll*pw[i-1]%mod;
	for (int i=1;i<=N;++i) pw2[i]=1ll*pw2[i-1]*pw[N]%mod;
	for (int i=1;i<=N;++i)
	{
		Adder(zdp[i],zdp[i-1]),Adder(zDP[i],zDP[i-1]),Adder(dp[i],zdp[i]),Adder(DP[i],zDP[i]),Adder(dp[i],pw[i-1]),Adder(DP[i],MD2(dp[i]-1));
		for (int j=2;j<=N/i;++j)
		{
			Adder(zdp[i*j],DP[i]),Adder(zdp[i*j],1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
			if (miu[j]==1) Adder(zDP[i*j],MD2(3ll*dp[i]%mod-2));
			else if (miu[j]==-1) Adder2(zDP[i*j],-MD2(3ll*dp[i]%mod-2));
			if ((i+1)*j<=N)
			{
				Adder2(zdp[(i+1)*j],-DP[i]),Adder2(zdp[(i+1)*j],-1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
				if (miu[j]==1) Adder2(zDP[(i+1)*j],-MD2(3ll*dp[i]%mod-2));
				else if (miu[j]==-1) Adder(zDP[(i+1)*j],MD2(3ll*dp[i]%mod-2));
			}
		}
	}
	for (int i=1;i<=length;++i)
	{
		if (tong[i]<=N) wdp[i]=dp[tong[i]],wDP[i]=DP[tong[i]],tmiu[i]=smiu[tong[i]];
		else
		{
			wdp[i]=get_pow(tong[i]-1),tmiu[i]=1;
			for (long long j=2,lst;j<=tong[i];j=lst+1)
			{
				lst=tong[i]/(tong[i]/j);
				Adder2(tmiu[i],-1ll*((lst-j+1)%mod)*tmiu[get(tong[i]/j)]%mod);
				Adder(wdp[i],1ll*((lst-j+1)%mod)*wDP[get(tong[i]/j)]%mod);
				Adder(wdp[i],1ll*MD2(S(lst)-S(j-1))%mod*MD2(2ll*MD(wdp[get(tong[i]/j)]+wDP[get(tong[i]/j)])%mod-1)%mod);
				Adder(wDP[i],1ll*MD2(tmiu[get(lst)]-tmiu[get(j-1)])%mod*MD2(3ll*wdp[get(tong[i]/j)]%mod-2)%mod);
			}
			Adder(wDP[i],MD2(wdp[i]-1));
		}
	}
	printf("%d\n",wdp[length]);
	return 0;
}