#include <bits/stdc++.h>
#define DIM 1000000
#define MOD 1048576
using namespace std;

ifstream fin ("12perm.in");
ofstream fout ("12perm.out");
int dp[10][10],aux[10];
int n,i,j;

int main (){

    fin>>n;
    if (n == 1){
        fout<<1;
        return 0;
    }
    if (n == 2){
        fout<<2;
        return 0;
    }

    /*dp[3][1] = 2;
    dp[3][2] = dp[3][3] = dp[3][4] = dp[3][5] = 1;
    dp[4][1] = 4;
    dp[4][2] = dp[4][3] = dp[4][4] = dp[4][5] = 2;*/

    dp[0][1] = 0, dp[0][2] = 1, dp[0][3] = 0, dp[0][4] = 1, dp[0][5] = 0; /// pt 2
    dp[1][1] = 2, dp[1][2] = 1, dp[1][3] = 1, dp[1][4] = 1, dp[1][5] = 1; /// pt 3
    dp[2][1] = 4, dp[2][2] = 2, dp[2][3] = 2, dp[2][4] = 2, dp[2][5] = 2; /// pt 4


    for (i=5;i<=n;i++){

        aux[1] = (dp[2][1] + dp[2][2] + dp[2][4])%MOD;
        aux[2] = (dp[2][2] + dp[2][3])%MOD;
        aux[3] = (1 + dp[0][2] + dp[0][3])%MOD;
        aux[4] = (dp[2][4] + dp[2][5])%MOD;
        aux[5] = (1 + dp[0][4] + dp[0][5])%MOD;

        for (j=1;j<=5;j++){
            dp[0][j] = dp[1][j];
            dp[1][j] = dp[2][j];
            dp[2][j] = aux[j];
        }
        /*
        dp[i][1] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4])%MOD;
        dp[i][2] = (dp[i-1][2] + dp[i-1][3])%MOD;
        dp[i][3] = (1 + dp[i-3][2] + dp[i-3][3])%MOD;
        dp[i][4] = (dp[i-1][4] + dp[i-1][5])%MOD;
        dp[i][5] = (1 + dp[i-3][4] + dp[i-3][5])%MOD;*/

    }
    int sol = 0;
    for (i=1;i<=5;i++){
        sol = sol + aux[i];
        if (sol >= MOD)
            sol -= MOD;
    }
    fout<<sol;

    return 0;
}