#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[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

    int sol = 0;
    for (i=5;i<=n;++i){

        aux[1] = dp[2][1] + dp[2][2] + dp[2][4];
        while (aux[1] >= MOD)
            aux[1] -= MOD;
        aux[2] = dp[2][2] + dp[2][3];
        if (aux[2] >= MOD)
            aux[2] -= MOD;

        aux[3] = 1 + dp[0][2] + dp[0][3];
        while (aux[3] >= MOD)
            aux[3] -= MOD;

        aux[4] = dp[2][4] + dp[2][5];
        if (aux[4] >= MOD)
            aux[4] -= MOD;

        aux[5] = 1 + dp[0][4] + dp[0][5];
        while (aux[5] >= MOD)
            aux[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];
            if (i == n){
                sol = sol + aux[j];
                if (sol >= MOD)
                    sol -= MOD;
            }
        }
    }

    fout<<sol;

    return 0;
}