#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 || n == 2){
        fout<<n;
        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] = dp[1][3] = dp[1][4] = dp[1][5] = 1; /// pt 3
    dp[2][1] = 4, dp[2][2] = dp[2][3] = dp[2][4] = 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];
        aux[2] = aux[4] = dp[2][2] + dp[2][3];
        aux[3] = aux[5] = 1 + dp[0][2] + dp[0][3];

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

        dp[0][1] = dp[1][1], dp[0][2] = dp[1][2], dp[0][3] = dp[1][3], dp[0][4] = dp[1][4], dp[0][5] = dp[1][5];
        dp[1][1] = dp[2][1], dp[1][2] = dp[2][2], dp[1][3] = dp[2][3], dp[1][4] = dp[2][4], dp[1][5] = dp[2][5];
        dp[2][1] = aux[1], dp[2][2] = aux[2], dp[2][3] = aux[3], dp[2][4] = aux[4], dp[2][5] = aux[5];
    }
    sol = aux[1] + 2*aux[2] + 2*aux[3];
    while (sol >= MOD)
        sol -= MOD;
    fout<<sol;

    return 0;
}