/* Code by pp_orange */
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define m_p(a,b) make_pair(a,b)
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf 0x7FFFFFFF
#define inff 9223372036854775807
#define rep(i,l,r) for(int i=l;i<r;++i)
#define repp(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r-1;i>=l;--i)
#define pper(i,r,l) for(int i=r;i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define p_q priority_queue
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define lb(x) ((x)&-(x))
#define lg(x) (31^__builtin_clz(x))
#define vi vector<int>
#define vii vector<pii >
const int mod = 998244353;
//#define int ll
const int intsz = sizeof(int);
using namespace std;
inline int rd(){
	int x(0),f(1);char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
inline void out(int X){
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) out(X/10);
	putchar(X%10+'0');
}
ll pw(ll x,int d){
	ll t = 1;
	for(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;
	return t;
}
#define MAX (1<<20)
namespace poly{
	#define CTZ __builtin_ctz
	const int de = 1;
	const int G = 3;
	const int Gi = pw(G,mod-2);
	typedef complex<ld> cplx;
	const ld pi = acos(-1);
	int getN(int n){
		int N = 1;
		while(N<=n)N<<=1;
		return N;
	}
	namespace polyTrs{
		int r[MAX];
		int nwsz = -1;
		
		void initR(int N,int lim){
			if(nwsz==lim)return ;
			nwsz = lim;
			rep(i,1,N)r[i] = (r[i>>1]>>1)|((i&1)<<(lim-1));
			return ;
		}
		
		void NTT(int *a,int N,int tp){
		//1:G, -1:Gi
		//need init R
			int x,y;
			if(de)assert(CTZ(N)==nwsz);
			const int g = tp==1?G:Gi;
			int omg;
			ll w;
			rep(i,0,N)if(r[i]<i)swap(a[i],a[r[i]]);
			for(int mid=1;mid<N;(mid<<=1)){
				omg = pw(g,(mod-1)/(mid<<1));
				for(int i=0,len=(mid<<1);i<N;i+=len){
					w = 1;
					for(int j=i;j<i+mid;++j,w=w*omg%mod){
						x = a[j];
						y = a[j+mid]*w%mod;
						a[j] = (x+y)%mod;
						a[j+mid] = (x-y+mod)%mod;
					}
				}
			}
			return ;
		}
		void FFT(cplx *a,int N,int tp){
		//1:G, -1:Gi
		//need init R
			if(de)assert(CTZ(N)==nwsz);
			int len;
			cplx w,omg,x,y;
			rep(i,0,N)if(r[i]<i)swap(a[r[i]],a[i]);
			for(int mid=1;mid<N;mid<<=1){
				len = mid<<1;
				omg = {cos(pi/mid),tp*sin(pi/mid)};
				for(int i=0;i<N;i+=len){
					w = 1;
					rep(j,i,i+mid){
						x = a[j];
						y = a[j+mid]*w;
						a[j] = x+y;
						a[j+mid] = x-y;
						w *= omg;
					}
				}
			}
			return ;
		}
	}using polyTrs::NTT,polyTrs::initR,polyTrs::FFT;
	
	namespace polyMul{
		int tmp[MAX];
		void Mul(int *a,int n,int *b,int m){
		//Mul(rlt,n,b,m) , won't destroy b
		//a^n and b^m
			memcpy(tmp,b,intsz*(m+1));
			int lim = 0;
			int N = 1;
			while(N<=n+m){
				N <<= 1;
				lim++;
			}
			initR(N,lim);
			NTT(a,N,1);
			NTT(b,N,1);
			ll Ni = pw(N,mod-2);
			rep(i,0,N)a[i] = (ll)a[i]*b[i]%mod*Ni%mod;
			NTT(a,N,-1);
			memcpy(b,tmp,intsz*(m+1));
			//rep(i,0,N)cout<<tmp[i]<<',';cout<<endl;
			memset(b+m+1,0,intsz*(N-(m+1)));
			return ;
		}
	}using polyMul::Mul;
	
	
	void Inv(int *b,int *a,int n){
	//Inv(output,input,n) mod x^n , won't destroy a
	//safe for *b
		static int f[MAX];
		if(de)assert(a[0]!=0);
		int N = 1;
		int lim = 0;
		b[0] = pw(a[0],mod-2);b[1] = 0;
		while(N<n){
			lim++;
			N <<= 1;
			memset(b+N,0,intsz*N);
			memcpy(f,a,intsz*N);
			memset(f+N,0,intsz*N);
			initR(N<<1,lim+1);
			NTT(b,N*2,1);
			NTT(f,N*2,1);
			rep(i,0,N*2)f[i] = b[i]*(2-(ll)b[i]*f[i]%mod+mod)%mod;
			NTT(f,N*2,-1);
			ll Ni = pw(N*2,mod-2);
			rep(i,0,N)b[i] = f[i]*Ni%mod;
			memset(b+N,0,intsz*N);
		}
		memset(b+n,0,intsz*(N-n));
	}
	void Sqrt(int *b,int *a,int n){
	//Sqrt(output,input,n) , mod x^n
		static int gi[MAX];
		static int f[MAX];
		static const int inv2 = pw(2,mod-2);
		int N = 1;
		int lim = 0;
		if(de)assert(a[0]==1);
		b[0] = 1;b[1] = 0;
		while(N<n){
			lim++;
			N <<= 1;
			memset(b+N,0,intsz*N);
			Inv(gi,b,N);
			memset(gi+N,0,intsz*N);
			memcpy(f,a,intsz*N);
			memset(f+N,0,intsz*N);
			initR(N*2,lim+1);
			NTT(gi,N*2,1);
			NTT(f,N*2,1);
			NTT(b,N*2,1);
			ll Ni = pw(N*2,mod-2);
			rep(i,0,N*2)b[i] = ((ll)f[i]*gi[i]%mod+b[i])*inv2%mod*Ni%mod;
			NTT(b,N*2,-1);
			memset(b+N,0,intsz*N);
		}
		memset(b+n,0,intsz*(N-n));
		return ;
	}
	
	void Dev(int *a,int n){
	//get Dev [ 0 , n )
		rep(i,0,n-1)a[i] = ((ll)a[i+1]*(i+1))%mod;
		a[n-1] = 0;
		return ;
	}
	
	namespace polyInter{
		int inv[MAX] = {0,1};
		int invsz = 1;
		void initInv(int sz){
			if(sz<=invsz)return ;
			repp(i,2,sz)inv[i] = (mod-(ll)inv[mod%i]*(mod/i)%mod);
			invsz = sz;
		}
		void Inter(int *a,int n){
		//get Inter [ 0 , n )
			initInv(n);
			per(i,n,1)a[i] = ((ll)a[i-1]*inv[i])%mod;
			a[0] = 0;
			return ;
		}
	}using polyInter::Inter;
	
	void Ln(int *b,int *a,int n){
	//Ln(out,in,n) , won't destroy a , mod x^n
		static int tmp[MAX];
		memcpy(tmp,a,intsz*n);
		int N = getN(n-1)*2;
		if(de)assert(a[0]==1);
		memcpy(b,a,intsz*N);
		Inv(a,b,n);
		Dev(b,n);
		
		initR(N,CTZ(N));
		NTT(a,N,1);
		NTT(b,N,1);
		ll Ni = pw(N,mod-2);
		rep(i,0,N)b[i] = ((ll)a[i]*b[i]%mod*Ni)%mod;
		NTT(b,N,-1);
		memset(b+n,0,intsz*(N-n));
		Inter(b,n);
		memcpy(a,tmp,intsz*n);
		memset(a+n,0,intsz*(N-n));
		return ;
	}
	
	void Exp(int *b,int *a,int n){
	//Exp(out,in,n) , won't destroy a
	// mod x^n
		static int c[MAX],d[MAX];
		if(de)assert(a[0]==0);
		int N = 1,lim = 0;
		b[0] = 1,b[1] = 0;
		while(N<n){
			N <<= 1;
			lim++;
			memset(b+N,0,intsz*N);
			Ln(c,b,N);
			memcpy(d,a,intsz*N);
			memset(d+N,0,intsz*N);
			initR(N*2,lim+1);
			NTT(b,N*2,1);
			NTT(c,N*2,1);
			NTT(d,N*2,1);
			ll Ni = pw(N*2,mod-2);
			rep(i,0,N*2)b[i] = (1ll-c[i]+d[i]+mod)%mod*b[i]%mod*Ni%mod;
			NTT(b,N*2,-1);
			memset(b+N,0,intsz*N);
		}
		memset(b+n,0,intsz*(N-n));
		return ;
	}
}
int U0[MAX],R0[MAX];
int A[MAX],B[MAX],C[MAX],D[MAX],E[MAX],Ctmp[MAX];
int a[MAX],b[MAX],c[MAX],d[MAX],e[MAX],f[MAX];
int F[MAX],Q[MAX],M[MAX],iM[MAX],tmp1[MAX],tmp2[MAX];
ll fac[MAX],ifac[MAX],idig[MAX];
void initComb(){
	fac[0] = 1;
	rep(i,1,MAX)fac[i] = (fac[i-1]*i)%mod;
	ifac[MAX-1] = pw(fac[MAX-1],mod-2);
	pper(i,MAX-2,0)ifac[i] = (ifac[i+1]*(i+1))%mod;
	rep(i,1,MAX)idig[i] = ifac[i]*fac[i-1]%mod;
	return ;
}
ll Comb(int x,int y){//choose y from x itms
	if(x<0||y<0||y>x)return 0;
	return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
signed main(){
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	initComb();
	int n = rd();
	int N = 2;
	R0[1] = 1;
	// U0[2] = 1;
	// R0[2] = 1;
	// U0[3] = 499122179;
	// R0[3] = 499122178;
//	499122179 499122178
	while(N<=n){
		// n
		N <<= 1;
		memset(A,0,intsz*N);
		memset(B,0,intsz*N);
		poly::Exp(A+1,R0,N-1);
		poly::Exp(B,U0,N);
		// cout<<"A : ";rep(i,0,)

		memcpy(Ctmp,U0,intsz*N/2);
		poly::Mul(Ctmp,N/2-1,R0,N/2-1);
		poly::Exp(C+1,Ctmp,N-1);

		
		memcpy(E,U0,intsz*N/2);
		memcpy(D,U0,intsz*N/2);
		poly::Mul(E,N/2-1,D,N/2-1);
		poly::Mul(D,N/2-1,E,N-1);
		memset(D+N,0,intsz*N/2);

		// cout<<"A : ";rep(i,0,N)cout<<A[i]<<' ';cout<<endl;
		// cout<<"B : ";rep(i,0,N)cout<<B[i]<<' ';cout<<endl;
		// cout<<"C : ";rep(i,0,N)cout<<C[i]<<' ';cout<<endl;
		// cout<<"D : ";rep(i,0,N)cout<<D[i]<<' ';cout<<endl;
		// cout<<"E : ";rep(i,0,N)cout<<E[i]<<' ';cout<<endl;

		// memcpy(a,U0,intsz*N/2);
		// a[0] = (a[0]+2)%mod;
		// poly::Mul(a,N/2-1,C,N-1);
		// memset(a+N,0,intsz*N/2);
		// a[0] = (a[0]+1+mod)%mod;
		// rep(i,0,N)b[i] = (a[i]-C[i]+mod)%mod;
		// b[0] = (b[0]-2+mod)%mod;
		// rep(i,0,N)c[i] = ((ll)R0[i]-U0[i]-b[i]+mod+mod)%mod;
		// c[0] = (c[0]+mod-1)%mod;
		memcpy(a,U0,intsz*N/2);
		a[0] = (a[0]+1)%mod;
		poly::Mul(a,N/2-1,R0,N/2-1);
		a[0] = (a[0]+1)%mod;
		poly::Mul(a,N-1,C,N-1);
		memset(a+N,0,intsz*N);
		a[0] = (a[0]+1)%mod;
		
		rep(i,0,N)b[i] = (U0[i]+E[i])%mod;
		poly::Mul(b,N-1,C,N-1);
		memset(b+N,0,intsz*N);
		b[0] = (b[0]-1+mod)%mod;

		memcpy(c,C,intsz*N);
		poly::Mul(c,N-1,U0,N-1);
		memset(c+N,0,intsz*N);
		rep(i,0,N)c[i] = ((ll)R0[i]-U0[i]-C[i]-c[i]+mod*4ll)%mod;

		rep(i,0,N)d[i] = (A[i]+E[i]*3ll)%mod;
		memcpy(e,U0,intsz*N/2);
		e[0] = (e[0]+1)%mod;
		poly::Mul(e,N/2-1,A,N-1);
		memset(e+N,0,intsz*N/2);
		e[0] = (e[0]-1+mod)%mod;
		rep(i,0,N)f[i] = ((ll)R0[i]-D[i]-e[i]+mod+mod)%mod;
		f[0] = (f[0]-1+mod)%mod;

		// cout<<"a : ";rep(i,0,N)cout<<a[i]<<' ';cout<<endl;
		// cout<<"b : ";rep(i,0,N)cout<<b[i]<<' ';cout<<endl;
		// cout<<"c : ";rep(i,0,N)cout<<c[i]<<' ';cout<<endl;
		// cout<<"d : ";rep(i,0,N)cout<<d[i]<<' ';cout<<endl;
		// cout<<"e : ";rep(i,0,N)cout<<e[i]<<' ';cout<<endl;
		// cout<<"f : ";rep(i,0,N)cout<<f[i]<<' ';cout<<endl;

		memcpy(tmp1,a,intsz*N);
		poly::Mul(tmp1,N-1,e,N-1);
		memset(tmp1+N,0,intsz*N);
		memcpy(tmp2,b,intsz*N);
		poly::Mul(tmp2,N-1,d,N-1);
		memset(tmp2+N,0,intsz*N);
		rep(i,0,N)M[i] = (tmp1[i]-tmp2[i]+mod)%mod;

		memcpy(tmp1,c,intsz*N);
		poly::Mul(tmp1,N-1,e,N-1);
		memset(tmp1+N,0,intsz*N);
		memcpy(tmp2,b,intsz*N);
		poly::Mul(tmp2,N-1,f,N-1);
		memset(tmp2+N,0,intsz*N);
		rep(i,0,N)F[i] = (tmp1[i]-tmp2[i]+mod)%mod;

		memcpy(tmp1,a,intsz*N);
		poly::Mul(tmp1,N-1,f,N-1);
		memset(tmp1+N,0,intsz*N);
		memcpy(tmp2,c,intsz*N);
		poly::Mul(tmp2,N-1,d,N-1);
		memset(tmp2+N,0,intsz*N);
		rep(i,0,N)Q[i] = (tmp1[i]-tmp2[i]+mod)%mod;

		poly::Inv(iM,M,N);
		poly::Mul(F,N-1,iM,N-1);
		memset(F+N,0,intsz*N);
		rep(i,N/2,N)U0[i] = F[i];

		poly::Mul(Q,N-1,iM,N-1);
		memset(Q+N,0,intsz*N);
		rep(i,N/2,N)R0[i] = Q[i];

		// cout<<"F : ";rep(i,0,N)cout<<F[i]<<' ';cout<<endl;
		// cout<<"Q : ";rep(i,0,N)cout<<Q[i]<<' ';cout<<endl;
		// cout<<"M : ";rep(i,0,N)cout<<M[i]<<' ';cout<<endl;
		// cout<<"iM : ";rep(i,0,N)cout<<iM[i]<<' ';cout<<endl;
	}
	// rep(i,0,N){
	// 	cout<<R0[i]<<' '<<U0[i]<<endl;
	// }cout<<endl;
	cout<<(U0[n]+R0[n])%mod*fac[n]%mod<<endl;
	return 0;
}
/**
0 0
1 0
1 1
499122179 499122178
166374065 665496239
623902737 457528672
108143186 981606976
525464880 500508714
*/