#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001];
long long t[20][550001],t1[20][550001],iv2,lim=(1<<17),tmp[1000001],tmp1[1000001],tmp2[1000001],ans[550001],f[10001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
long long id[2100001],lg,G=3;
void ntt(long long *A,long long *B,long long fl)
{
	for(int i=0;i<lim;i++) B[i]=A[i];
	for(int i=0;i<lim;i++) if(i<id[i]) swap(B[i],B[id[i]]);
	for(int i=1;i<lim;i*=2)
	{
		long long un=pow_(G,(mod-1)/(i*2));
		if(fl==-1) un=pow_(un,mod-2);
		for(int j=0;j<lim;j+=i*2)
		{
			long long om=1;
			for(int k=0;k<i;k++)
			{
				long long x=B[j+k],y=B[i+j+k]*om%998244353;
				B[j+k]=(x+y)%998244353,B[i+j+k]=(x-y+998244353)%998244353;om=om*un%998244353;
			}
		}
	}
}
void mul(long long *A,long long *B,long long *C)
{
	ntt(A,tmp1,1);ntt(B,tmp2,1);
	for(int i=0;i<lim;i++) tmp1[i]=tmp1[i]*tmp2[i]%mod;
	ntt(tmp1,tmp2,-1);
	long long un=pow_(lim,mod-2);
	for(int i=0;i<lim;i++) C[i]=tmp2[i]*un%mod;
}
int main()
{
//	freopen("1.in","r",stdin);
	srand((unsigned)(time(0)^(*new int)));
	fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	iv2=pow_(2,mod-2);
	lg=log2(lim);for(int i=0;i<lim;i++) id[i]=(id[i>>1]>>1)+((i&1)<<(lg-1));
	scanf("%lld",&a);
	for(int i=1;i<=a;i++) t[0][i]=inv[i]*pow_(iv2,i)%mod;
	for(int i=0;i<=a;i++) t1[0][i]=inv[i]*pow_(iv2,i)%mod;
	mul(t[0],t1[0],tmp);
	for(int i=0;i<=a;i++) t1[0][i]=tmp[i];
	long long tt=iv2;f[0]=tt;
	for(int i=1;i<=16;i++)
	{
		long long uu=1;
		for(int j=0;j<=a;j++) tmp[j]=t[i-1][j]*uu%mod,uu=uu*tt%mod;
		for(int j=a+1;j<lim;j++) tmp[j]=0;
		mul(t[i-1],tmp,t[i]);
		for(int j=a+1;j<lim;j++) t[i][j]=0;
		uu=1;
		for(int j=0;j<=a;j++) tmp[j]=t1[i-1][j]*uu%mod,uu=uu*tt%mod;
		mul(t[i-1],tmp,t1[i]);
		uu=1;
		for(int j=a+1;j<lim;j++) t1[i][j]=0;
		for(int j=0;j<=a;j++) t1[i][j]=(t1[i][j]+t1[i-1][j])%mod;
		tt=tt*tt%mod;
		f[i]=tt;
	}
//	cout<<t1[1][a]<<" ";
	tt=1;
	for(int i=0;i<=17;i++)
	{
		if((1<<i)&a)
		{
			long long uu=1;
			for(int j=0;j<=a;j++) ans[j]=ans[j]*uu%mod,uu=uu*f[i]%mod;
			mul(ans,t[i],tmp);
			for(int j=0;j<=a;j++) ans[j]=(tmp[j]+t1[i][j])%mod;
		}
	}
	an=ans[a];
	printf("%lld",(an*fac[a]%mod+mod)%mod);
	return 0;
}