#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll	a[5][5],ans[5];
ll n;
void ad(){
	ll s[5];
	for(int i=1;i<=3;i++)s[i]=ans[i],ans[i]=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			ans[i]=(ans[i]+s[j]*a[i][j])%mod;
		}
	}
}
void cf(){
	ll s[5][5];
	for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)s[i][j]=a[i][j],a[i][j]=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int u=1;u<=3;u++){
				a[i][j]=(a[i][j]+s[i][u]*s[u][j]%mod)%mod;
			}
		}
	}
}
int main(){
	freopen("X.in","r",stdin);
	freopen("X.out","w",stdout);
	a[1][1]=2,a[2][3]=1,a[3][1]=1,a[3][2]=1;
	ans[1]=2,ans[2]=0,ans[3]=1;
	n=read();
	n--;
	while(n){
		if(n&1)ad();
		cf();
//		for(int i=1;i<=3;i++){
//			for(int j=1;j<=3;j++)cout<<a[j][i]<<" ";
//			cout<<endl;
//		}
//		cout<<"------------\n";
		n/=2;
	}
	cout<<ans[3];
	return 0;
}