#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
typedef vector<ll> poly;
const int mb=18;//can change !!!!
ll roots[1<<mb];
int rev[1<<mb];
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
void operator<<(ostream& out,poly y){
	for(auto c:y) out << c*512*6%mod << ' ';
}
poly operator+(poly x,poly y){
	int n=max(x.size(),y.size());
	x.resize(n);y.resize(n);
	for(int i=0; i<n ;i++){
		x[i]+=y[i];
		if(x[i]>=mod) x[i]-=mod;
	}
	return x;
}
poly operator-(poly x,poly y){
	int n=max(x.size(),y.size());
	x.resize(n);y.resize(n);
	for(int i=0; i<n ;i++){
		x[i]+=mod-y[i];
		if(x[i]>=mod) x[i]-=mod;
	}
	return x;
}

void pre(){
	roots[0]=1;
	roots[1]=pw(15311432,1<<(23-mb));
	for(int i=1; i<(1<<mb) ;i++) roots[i]=roots[i-1]*roots[1]%mod;
}
void fft(poly &p){
	int n=p.size();
	roots[0]=1;
	int m=(1<<mb)/n;
	for(int i=1; i<n ;i++){
		rev[i]=rev[i/2]/2+((i&1)*n/2);
		if(i<rev[i]) swap(p[i],p[rev[i]]);
	}
	for(int k=1; k<n ;k*=2){
        for(int i=0; i<n ;i+=2*k){
            int cur=0,step=n/(2*k);
            for(int j=0; j<k;j++,cur+=step){
                ll x=p[i+j];
                ll y=p[i+j+k]*roots[cur*m]%mod;
                p[i+j]=(x+y>=mod?x+y-mod:x+y);
				p[i+j+k]=(x>=y?x-y:x+mod-y);
            }
        }
    }
}
poly operator*(poly x,poly y){
	int n=1;
	while(n<x.size()+y.size()-1) n*=2;
	x.resize(n,0);y.resize(n,0);
	fft(x);fft(y);
	for(int i=0; i<n ;i++) x[i]=x[i]*y[i]%mod;
	reverse(x.begin()+1,x.end());
	fft(x);
	ll inv=pw(n,mod-2);
	for(int i=0; i<n ;i++) x[i]=x[i]*inv%mod;
	while(x.size()>1 && x.back()==0) x.pop_back();
	return x;
}/*
vector<ll>multiply2(vector<ll>x,vector<ll>y){
	vector<ll>z;z.resize(x.size()+y.size()-1);
	for(auto c:z) c=0;
	for(int i=0; i<x.size() ;i++){
		for(int j=0; j<y.size() ;j++){
			z[i+j]=(z[i+j]+x[i]*y[j])%mod;	
		}
	}
	return z;
}*/
int n;
ll f[100005],inf[100005],pc[100005];
pair<poly,poly>aespa(int m){//sum,prod
	if(m==0){
		pair<poly,poly>res;
		res.fi={0};res.fi.resize(n+1);
		res.se={1};res.se.resize(n+1);
		return res;
	}
	if(m%2){
		auto res=aespa(m-1);
		poly cur(n+1);
		ll frog=1;
		for(int i=1; i<=n ;i++){
			frog=frog*pc[m]%mod;
			cur[i]=frog*inf[i]%mod;
		}
		
		res.se=res.se*cur;
		res.se.resize(n+1);
		cur[0]=1;
		res.fi=res.fi+res.se*cur;
		res.fi.resize(n+1);
		return res;
	}
	else{
		auto res=aespa(m/2);
		poly rs(n+1),rp(n+1);
		ll frog=1;
		for(int i=0; i<=n ;i++){
			rs[i]=res.fi[i]*frog%mod;
			rp[i]=res.se[i]*frog%mod;
			frog=frog*pc[m/2]%mod;
		}
		rs=rs*res.se;
		res.fi=res.fi+rs;
		res.se=res.se*rp;
		res.fi.resize(n+1);
		res.se.resize(n+1);
		return res;
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);pre();
	cin >> n;
	f[0]=pc[0]=1;
	for(int i=1; i<=n ;i++){
		f[i]=f[i-1]*i%mod;
		pc[i]=pc[i-1]*(mod+1)/2%mod;
	}
	inf[n]=pw(f[n],mod-2);
	for(int i=n; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
	auto res=aespa(n);
	ll ans=res.fi[n]*f[n]%mod;
	cout << ans << '\n';
}