#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
#define int LL
using namespace std;
const LL N=2e10+5;
const int M=2e6,K=N/M,Mod=998244353;
LL n;
int vp[M+5],pw2[M+5],mu[M+5];
int smu[M+5],f[M+5],g[M+5],h[M+5],q[M+5],w[M+5];
int nsmu[K+5],nf[K+5],ng[K+5],nh[K+5],nq[K+5],nw[K+5];
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline void sieve(int n){
	fill(mu+1,mu+n+1,1);
	for(int i=2;i<=n;++i)if(!vp[i]){
		for(int j=i;j<=n;j+=i)mu[j]*=-1,vp[j]=1;
		for(int j=i*i;j<=n;j+=i*i)mu[j]=0;
	}
}
inline int Smu(LL n){
	if(n<=M)return smu[n];
	const int p=::n/n;
	if(nsmu[p])return nsmu[p];
	const int B=sqrtl(n);
	LL z=1;LL l=B,r;
	for(int i=B;i>1;--i,l=r)r=n/i,z-=(r-l)*smu[i]+Smu(r);
	return z-=n-l,nsmu[p]=z%Mod;
}
inline int Q(LL n){
	if(n<=M)return q[n];
	const int p=::n/n;
	if(nq[p])return nq[p];
	int z=qpow(2,(n/2+1)%(Mod-1))-2;
	if(n%2==0)z-=qpow(2,(n/2-1)%(Mod-1));
	return nq[p]=(z-n+1)%Mod;
}
inline int W(LL n){
	if(n<=M)return w[n];
	const int p=::n/n;
	if(nw[p])return nw[p];
	return nw[p]=qpow(2,(n-1)%(Mod-1));
}
inline int F(LL n);
inline int G(LL n);
inline int H(LL n);
inline int F(LL n){
	if(n<=M)return f[n];
	const int p=::n/n;
	if(nf[p])return nf[p];
	const int B=sqrtl(n);
	int &z=nf[p],i=B;LL l=B,r;
	for(z=0;i>1;--i,l=r)
		r=n/i,z=(z+1ll*g[i]*(Q(r)-Q(l))+(r-l)%Mod*h[i])%Mod,
		z=(z+1ll*G(r)*q[i]+H(r))%Mod;
	z=(z+1ll*G(1)*(Q(n)-Q(l))+1ll*H(1)*(n-l))%Mod;
	return z;
}
inline int G(LL n){
	if(n<=M)return g[n];
	const int p=::n/n;
	if(ng[p])return ng[p];
	return ng[p]=(2ll*(F(n)+H(n))+qpow(2,n%(Mod-1))-1)%Mod;
}
inline int H(LL n){
	if(n<=M)return h[n];
	const int p=::n/n;
	if(nh[p])return nh[p];
	const int B=sqrtl(n);
	int &z=nh[p],i=B;LL l=B,r;
	for(z=(1-2ll*F(n)-qpow(2,n%(Mod-1)))%Mod;i>=1;--i,l=r)
		r=n/i,z=(z+(Smu(r)-Smu(l))*(3ll*(f[i]-w[i])-2))%Mod,
		z=(z+mu[i]*(3ll*(F(r)-W(r))-2))%Mod;
	return z;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>n,sieve(M);
	pw2[0]=1;
	for(int i=1;i<=M;++i)pw2[i]=pw2[i-1]*2%Mod;
	for(int i=1;i<=M;++i){
		if(i>1)for(int j=1;i*j<=M;++j)if(mu[j])
			g[i*j]=(g[i*j]+6ll*mu[j]*(f[i]+pw2[i-2]))%Mod,
			h[i*j]=(h[i*j]+3ll*mu[j]*(f[i]+pw2[i-2]))%Mod;
		g[i]=(g[i]+(mu[i]-f[i])*2ll-pw2[i-1])%Mod,
		h[i]=(h[i]+mu[i]-f[i]*2ll-pw2[i-1])%Mod;
		for(int j=2;i*j<=M;++j)f[i*j]=(f[i*j]+h[i]+(pw2[j/2-1]-1ll)*g[i])%Mod;
	}
	for(int i=1;i<=M;++i)
		w[i]=i>1?w[i-1]*2%Mod:1,
		q[i]=i>1?(w[i/2]-1+q[i-1])%Mod:0,
		f[i]=(f[i]+f[i-1])%Mod,
		g[i]=(g[i]+g[i-1])%Mod,
		h[i]=(h[i]+h[i-1])%Mod,
		smu[i]=smu[i-1]+mu[i];
	int ans=(qpow(2,(n-1)%(Mod-1))+F(n))%Mod;
	cout<<(ans<0?ans+Mod:ans)<<'\n';
    return 0;
}
/*
*/