#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
namespace fft{
const int maxn=(1<<21);
int proot=step(3,7*17*4);
int prekw[maxn];
bool isprek=false;
void prek(){
    if(isprek)return;
    isprek=true;
    prekw[0]=1;
    for(int i=1;i<maxn;i++){
        prekw[i]=mul(prekw[i-1],proot);
    }
}
void fft(vector<int>&a,bool invert){

    prek();

    int n=a.size();
    int j=0;
    for(int i=1;i<n;i++){
        int bit=n>>1;
        for(;bit&j;bit>>=1)j^=bit;
        j^=bit;
        if(i<j)swap(a[i],a[j]);
    }

    for(int len=2;len<=n;len<<=1){
        int hlen=len>>1;
        for(int i=0;i<n;i+=len){
            int curr=0;
            int d=maxn/len;
            if(invert)d=maxn-d;
            for(int j=0;j<hlen;j++){
                int pom1=a[i+j];
                int pom2=mul(a[i+j+hlen],prekw[curr]);

                a[i+j]=add(pom1,pom2);
                a[i+j+hlen]=sub(pom1,pom2);

                curr+=d;
                if(curr>=maxn)curr-=maxn;
            }
        }
    }

    if(invert){
        int invn=invv(n);
        for(int i=0;i<n;i++)a[i]=mul(a[i],invn);
    }

}

}

void print(vector<int> a){
	printf("[ ");
	for(int i=0;i<sz(a);i++){
		printf("%i",a[i]);
		if(i==sz(a)-1)printf(" ]");
		else printf(", ");
	}
}
vector<int> mul(vector<int> a,vector<int> b){
	if(sz(a)<5||sz(b)<5){
		vector<int> ans(sz(a)+sz(b)-1);
		for(int i=0;i<sz(a);i++){
			for(int j=0;j<sz(b);j++){
				ans[i+j]=add(ans[i+j],mul(a[i],b[j]));
			}
		}
		return ans;
	}
    int sz=1;
    while(sz<a.size()+b.size())sz*=2;
    a.resize(sz);
    b.resize(sz);
    fft::fft(a,false);
    fft::fft(b,false);
    for(int i=0;i<sz;i++)a[i]=mul(a[i],b[i]);
    fft::fft(a,true);
    while(a.size() && a.back()==0)a.pop_back();
    return a;
}
vector<int> mul(vector<int> a,int x){
	for(int i=0;i<sz(a);i++)a[i]=mul(a[i],x);
	return a;
}
vector<int> add(vector<int> a,vector<int> b){
	vector<int> c(max(sz(a),sz(b)));
	for(int i=0;i<sz(a);i++)c[i]=add(c[i],a[i]);
	for(int i=0;i<sz(b);i++)c[i]=add(c[i],b[i]);
    return c;
}
vector<int> divx(vector<int> &a){
	vector<int> c(sz(a)-1);
	for(int i=1;i<sz(a);i++)c[i-1]=a[i];
	return c;
}
int main()
{
	int k;
	cin >> k;
	vector<int> p0={0,1},p1={0,1};
	vector<int> f0={0,1},f1={0,0},f2={0,0};
	vector<int> np0,np1,nf0,nf1,nf2;
	vector<int> divp0,divp1;
	int fl=2;
	vector<int> v11={1,1};
	vector<int> v01m1={0,1,-1};
	vector<int> v1={1};
	vector<int> v0m1={0,-1};
	vector<int> v00m1={0,0,-1};
	auto trans1=[&](){
		np0=add(mul(p0,v11),v01m1);
		np1=mul(p1,v11);
		nf0=add(mul(p0,p0),add(mul(f0,2),v01m1));
		nf1=add(mul(mul(p0,p1),2),mul(f1,2));
		nf2=add(mul(p1,p1),mul(f2,2));
		fl=add(fl,fl);
		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
	};
	auto trans2=[&](){
		divp0=add(divx(p0),add(p0,v0m1));
		divp1=divx(p1);
		np0=add(mul(p0,add(v1,divp1)), mul(p1,add(p0,v0m1)));
		
		divp1=add(divp1,p1);
		np1=mul(p1,divp1);
		
		nf0=add(f0,
		add(mul(f1,divp0),
		add(mul(f2,mul(divp0,divp0)),
		add(mul(f0,fl),
		mul(add(mul(p0,p0),v00m1),fl/2)
		))));
		
		nf1=add(mul(f1,divp1),
		add(mul(mul(f2,2),mul(divp0,divp1)),
		add(mul(f1,fl),
		mul(mul(p0,p1),fl)
		)));
		
		nf2=add(mul(f2,mul(divp1,divp1)),
		add(mul(f2,fl),
		mul(mul(p1,p1),fl/2)
		));
		
		p0=np0;p1=np1;f0=nf0;f1=nf1;f2=nf2;
		fl=mul(fl,fl);
	};
	function<void(int)> rec=[&](int t){
		if(t==1)return;
		if(t%2==0){
			rec(t/2);
			trans2();
		}
		else{
			rec(t/2);
			trans2();
			//printf("p0: ");print(p0);printf("\np1: ");print(p1);printf("\nf0: ");print(f0);printf("\nf1: ");print(f1);printf("\nf2: ");print(f2);printf("\n");
			trans1();
		}
	};
	rec(k);
	/*for(int i=1;i<k;i++){
		trans1();
		printf("p0: ");print(p0);printf("\np1: ");print(p1);printf("\nf0: ");print(f0);printf("\nf1: ");print(f1);printf("\nf2: ");print(f2);printf("\n");
	}*/
	vector<int> ans=add(f0,add(add(f1,{0,fl}),f2));
	/*for(int i=0;i<2*k-2;i++){
		printf("%i ",ans[i+1]);
	}
	printf("\n");*/
	return 0;
}