#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5,mod=998244353,I2=(mod+1)>>1;
int n,f[N],g[N],h[N],pw[N],pr[N],mu[N];bool v[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 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;
}
inline int F(int x)
{
	return (3ll*(f[x]+pw[max(x-2,0)]))%mod;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
	init(n);int M=n;
	for(int i=pw[0]=1;i<=M;i++) pw[i]=md(pw[i-1]<<1);g[1]=1;
	for(int i=2;i<=M;i++)
	{
		f[i]=md(f[i]+pw[i/2-1]-1);
		g[i]=md(g[i]+mod-(2ll*f[i]+pw[i-1]-2*mu[i])%mod);
		h[i]=md(h[i]+mod-(2ll*f[i]+pw[i-1]-mu[i])%mod);
		for(int j=i;j<=M;j+=i)
			g[j]=(g[j]+2ll*(mu[j/i]+mod)*F(i))%mod,
			h[j]=(h[j]+1ll*(mu[j/i]+mod)*F(i))%mod;
		for(int j=i+i;j<=M;j+=i)
			f[j]=(f[j]+h[i]+1ll*g[i]*(pw[j/(i<<1)-1]-1))%mod;
	}
	for(int i=1;i<=n;i++) ad(f[i],f[i-1]),ad(g[i],g[i-1]),ad(h[i],h[i-1]);
	// for(int i=1;i<=n;i++) cout<<f[i]<<" "<<g[i]<<" "<<h[i]<<"\n";
	// 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;
	// 	}
	// 	h[i]=(-2ll*f[i]-ksm(2,i)+1+s)%mod;
	// 	h[i]=(mod+h[i])%mod;
	// 	g[i]=(-2ll*f[i]-ksm(2,i)+1+2ll*s)%mod;
	// 	g[i]=(mod+g[i])%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<<(f[n]+ksm(2,n-1))%mod;
	return 0;
}