#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=2e6+5,mod=998244353,I2=(mod+1)>>1,I32=I2+1;
int U,pw[N],pr[N/13],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(LL 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;int w=TO(k),r=(k+1)%mod;
	if(n&1) return 2ll*(pw[w]-r+mod)%mod;
	return (1ll*pw[w]*I32+2ll*(mod-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);auto [f,g,h]=sol(n/i);
		F=(F+1ll*g*(S(j)-S(i-1)+mod)+(j-i+1)%mod*h)%mod;
		int x=(3ll*f+1ll*I32*pw[TO(n/i)]-2+mod)%mod*(Mu(j)-Mu(i-1)+mod)%mod;
		G=(G+2ll*x)%mod;H=md(H+x);
	}int x=(2ll*(mod-F)-pw[w]+1+mod)%mod;
	G=md(G+x),H=md(H+x);x=(3ll*F+1ll*I32*pw[w]-2+mod)%mod;
	G=(G+2ll*x)%mod;H=md(H+x);
	return b[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=powl(n/logl(n),2.0/3)*2);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));
	cout<<(sol(n).f+ksm(2,(n-1)%(mod-1)))%mod;
	return 0;
}