#include<bits/stdc++.h>
#define de fprintf(stderr,"on-%d\n",__LINE__)
//#define int long long
#define fr(i,a,b) for(int i(a),end##i(b);i<=end##i;i++)
#define fd(i,a,b) for(int i(a),end##i(b);i>=end##i;i--)
#define vec vector<int>
using namespace std;
const int maxn=2e6+5,mod=998244353,G=3;
inline int upd(const int &x){
	if(x<0)return x+mod;
	if(x>=mod)return x-mod;
	return x;
}
inline void add(int &x,const int &y){
	x=upd(x+y);
}
int ksm(int x,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;
		k>>=1;
	}
	return ans;
}
int jc[maxn],iv[maxn];
void init(int n){
	jc[0]=1;
	fr(i,1,n)jc[i]=1ll*jc[i-1]*i%mod;
	iv[n]=ksm(jc[n],mod-2);
	fd(i,n-1,0)iv[i]=1ll*iv[i+1]*(i+1)%mod;
}
int ny(int n){
	return 1ll*iv[n]*jc[n-1]%mod;
}
const int invg=ksm(G,mod-2);
int rev[maxn];
void F(int *f,int n,int h){
	fr(i,0,n-1)if(rev[i]<i)swap(f[rev[i]],f[i]);
	for(int p=1;p<n;p<<=1){
		int wn=ksm(h==1?G:invg,(mod-1)/(p<<1));	
		for(int i=0;i<n;i+=p<<1)
			for(int k=i,w=1;k<i+p;k++,w=1ll*w*wn%mod){
				int x=f[k],y=1ll*f[k+p]*w%mod;	
				f[k]=upd(x+y);
				f[k+p]=upd(x-y);
			}
	}
	if(h==-1){
		int invn=ny(n);
		fr(i,0,n-1)f[i]=1ll*f[i]*invn%mod;
	}
}
vector<int> operator *(const vector<int>& A,const vector<int>& B){
	static int a[maxn],b[maxn]; 
	int N=1;
	while(N-1<=A.size()-1+B.size()-1)N<<=1;
	fr(i,1,N)rev[i]=(rev[i>>1]>>1)|(i&1?N>>1:0);
	fr(i,0,N-1)a[i]=b[i]=0;
	fr(i,0,A.size()-1)a[i]=A[i];fr(i,0,B.size()-1)b[i]=B[i];
	F(a,N,1);F(b,N,1);
	fr(i,0,N-1)a[i]=1ll*a[i]*b[i]%mod;
	F(a,N,-1);
	vector<int> C;C.resize(A.size()+B.size()-1);
	fr(i,0,C.size()-1)C[i]=a[i];
	return C;
}
vector<int> operator -(vector<int> A,const vector<int>&B){
	if(B.size()>A.size())A.resize(B.size());
	fr(i,0,B.size()-1)add(A[i],-B[i]);
	return A;
}
vector<int> operator +(vector<int> A,const vector<int>&B){
	if(B.size()>A.size())A.resize(B.size());
	fr(i,0,B.size()-1)add(A[i],B[i]);
	return A;
}
vector<int> operator *(vector<int> A,const int &x){
	fr(i,0,A.size()-1)A[i]=1ll*A[i]*x%mod;
	return A;
}
vector<int> inv(vector<int> A,int N){
	vector<int> F,f0;	
	F.push_back(ksm(A[0],mod-2));
	for(int n=2;n>>1<N;n<<=1){
		f0=F;
		F=f0*2-f0*f0*A;
		F.resize(n);
	}
	F.resize(N);
	return F;
}

vector<int> D(vector<int> A){
	fr(i,0,A.size()-2)A[i]=1ll*A[i+1]*(i+1)%mod;
	A.resize(A.size()-1);
	return A;	
}
vector<int> Int(vector<int> A){
	A.resize(A.size()+1);
	fd(i,A.size()-1,1)A[i]=1ll*A[i-1]*ny(i)%mod;
	A[0]=0;
	return A;
}
vector<int> ln(const vector<int> &A,int n){
	vector<int> C=D(A)*inv(A,n);
	C.resize(n);
	C=Int(C);
	C.resize(n);	
	return C;
}
vector<int> exp(const vector<int> &A,int N){
	vector<int> f0,F,G;
	F.push_back(1);
	for(int n=2;n>>1<N;n<<=1){
		f0=F;
		G.resize(n);
		fr(i,0,G.size()-1)G[i]=i<(int)A.size()?A[i]:0;
		F=f0-(ln(f0,n)-G)*f0;
		F.resize(n);
	}
	F.resize(N);
	return F;
}
void out(vec A){
	fr(i,0,A.size()-1)cout<<A[i]<<' ';cout<<'\n';
}
vec solve(int N){
	vector<int> F,f0,A,B,T;
	F.push_back(1);
	for(int n=2;n>>1<N;n<<=1){
		f0=F;
		B=f0*f0;B.resize(n);A=B;A=A*f0;A.resize(n);
		T.resize(n);
		T[0]=1;
		fr(i,1,n-1)T[i]=i<=f0.size()?upd(-f0[i-1]):0;
		T=inv(T,n);
		B[0]=3ll*B[0]%mod;
		fr(i,1,n-1)B[i]=upd((3ll*B[i]-2ll*A[i-1])%mod);
		A=A*T;A.resize(n);
		//out(A);
		T=T*T;T.resize(n);
		//out(T);
		B=B*T;B.resize(n);
		//out(B);
		A=A-B*f0;A.resize(n);
		//out(A);
		B=Int(B);B.resize(n);
		fr(i,0,n-1)B[i]=upd(-B[i]);
		B=exp(B,n);
		A=A*B;A.resize(n);
		//out(A);
		A=Int(A);A.resize(n);
	//	out(A);
		B=inv(B,n);
		A[0]=1;
		//out(B);
		F=A*B;F.resize(n);
		//out(F);
	}
	//fr(i,0,N-1)printf("%lld ",F[i]);cout<<'\n';
	return F;
}
signed main(){
#ifdef pig
	freopen("pig.in","r",stdin);
	freopen("pig.out","w",stdout);
#endif
	int n;
	vector<int> A;
	scanf("%d",&n);
	int N=1;
	while(N<n+1)N<<=1;
	init(N<<2);
	cout<<1ll*solve(N)[n]*jc[n]%mod;
	/*A.resize(n);
	fr(i,0,n-1)scanf("%lld",&A[i]);
	A=exp(A,n);
	fr(i,0,n-1)printf("%lld ",A[i]);*/
	return 0;
}