// created:  2024-09-26 13:04:19
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
constexpr int N=5005,MOD=998244353;
void reduce(int &x){(x>=MOD)&&(x-=MOD);}
int qpow(ull a,int b,ull c=1)
{
	for(;b;b>>=1,(a*=a)%=MOD)if(b&1)(c*=a)%=MOD;
	return (int)c;
}
struct matrix
{
	int t,a[3][3][N];
};
void mul(matrix &c,const matrix &a,const matrix &b)
{
	static ull d[3][3][N];
	F(i,0,3)F(j,0,3)memset(d[i][j],0,sizeof(ull)*(a.t+b.t+1));
	F(i,0,3)F(j,0,3)F(k,0,3)
	{
		F(i0,0,a.t+1)
		{
			F(i1,0,b.t+1)d[i][k][i0+i1]+=(ull)a.a[i][j][i0]*b.a[j][k][i1];
			if(!(~i0&15))F(i1,0,a.t+b.t+1)d[i][k][i1]%=MOD;
		}
	}
	c.t=a.t+b.t;
	F(i,0,3)F(j,0,3)F(k,0,a.t+b.t+1)c.a[i][j][k]=(int)(d[i][j][k]%MOD);
}
int n,fac[N],invfac[N],f[N];
matrix a,b;
int main()
{
	F(i,fac[0]=1,N)fac[i]=(int)((ull)fac[i-1]*i%MOD);
	invfac[N-1]=qpow(fac[N-1],MOD-2);
	for(int i=N;--i;)invfac[i-1]=(int)((ull)invfac[i]*i%MOD);
	read(n);
	a.t=0;
	F(i,0,3)a.a[i][i][0]=1;
	b.t=1;
	F(i,0,3)b.a[i][0][1]=1;
	F(i,0,2)b.a[i][i+1][0]=1;
	for(int i=n;i;)
	{
		if(i&1)mul(a,a,b);
		if((i>>=1))mul(b,b,b);
	}
	F(i,0,3)F(j,0,n+1)reduce(f[j]+=a.a[i][i][j]);
	int ans=n+1;
	F(i,0,n+1)ans=(int)((ans+(ull)(MOD-f[i])*invfac[n]%MOD*fac[i]%MOD*fac[n-i])%MOD);
	printf("%d\n",ans);
	return 0;
}