statements
solutions
值的一提的是如果直接用矩阵快速幂的话有超时的风险，可以使用十进制优化的是矩阵快速幂，或者使用欧拉降幂，注意到转移矩阵是可对角化的，可以直接在指数上模
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,mod0=998244352;
int qpow(int b,int p=mod-2){
int res=1;
while(p){
if(p&1) res=res*b%mod;
p>>=1;
b=b*b%mod;
}
return res;
}
signed main( )
{
string s;
cin>>s;
int n=0;
for(int i=0;s[i];i++)
n=n*10%mod0+(s[i]-'0');
int ans=qpow(2,n+1);
if((s.back()-'0')%2==0) ans++;
else ans--;
ans=ans*qpow(3)%mod;
cout<<ans<<'\n';
return 0;
}
