#include <bits/stdc++.h>

using namespace std;

int dp[2000][2000];

typedef long long LL;

int main()

{

    LL c[50];

    c[0]=0;

    c[1]=1;

    c[2]=1;

    for(int i=2; i<50; i++) c[i] = c[i-1]+c[i-2];

    dp[0][0]=1;

    for(int i=0; i<=40; i++){

        for(int j=1; j<=40; j++){

            for(int k=c[i]; k<=1000; k++){

                dp[j][k] = dp[j][k] + dp[j-1][k-c[i]];

            }

        }

    }

    for(int i=1; i<=40; i++)

        for(int j=1; j<=1000; j++)

    if(dp[i][j]==0){

        printf("%d\n", j);

        break;

    }

}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 998244353;

struct Matrix{

    LL a[3][3];

    void set1(){

        memset(a, 0, sizeof(a));

    }

    void set2(){

        set1();

        for(int i=0; i<3; i++) a[i][i]=1;

    }

    void set3(){

        a[0][0]=3,a[0][1]=-1,a[0][2]=1;

        a[1][0]=1,a[1][1]=0,a[1][2]=0;

        a[2][0]=0,a[2][1]=0,a[2][2]=1;

    }

    void set4(){

        set1();

        a[0][0]=12;

        a[1][0]=4;

        a[2][0]=1;

    }

};

Matrix operator*(const Matrix &a, const Matrix &b){

    Matrix res;

    res.set1();

    for(int i=0; i<3; i++){

        for(int j=0; j<3; j++){

            for(int k=0; k<3; k++){

                res.a[i][j] = (res.a[i][j]+a.a[i][k]*b.a[k][j]+mod)%mod;

            }

        }

    }

    return res;

}

Matrix qsm(Matrix a, int n){

    Matrix res;

    res.set2();

    while(n){

        if(n&1) res=res*a;

        a=a*a;

        n/=2;

    }

    return res;

}

int main()

{

    int n;

    while(scanf("%d", &n)!=EOF)

    {

        if(n==1) printf("4\n");

        else if(n==2) puts("12");

        else{

            Matrix a,b;

            a.set3();

            b.set4();

            a = qsm(a,n-2);

            a=a*b;

            printf("%lld\n", (a.a[0][0]+mod)%mod);

        }

    }

    return 0;

}