#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("12-perm.in");
ofstream fout("12-perm.out");
long long dp[11][15000001],n,i,s=0,j;
const int mod=1048576;
int main()
{
    fin>>n;
    dp[1][2]=1;
    dp[2][2]=1;
    dp[3][2]=0;
    dp[4][2]=0;
    dp[5][2]=0;
    dp[6][2]=0;
    dp[7][2]=0;
    dp[8][2]=0;
    dp[9][2]=0;
    dp[10][2]=0;
    dp[1][3]=1;
    dp[2][3]=1;
    dp[3][3]=0;
    dp[4][3]=0;
    dp[5][3]=0;
    dp[6][3]=0;
    dp[7][3]=1;
    dp[8][3]=1;
    dp[9][3]=1;
    dp[10][3]=1;
    for(i=4;i<=n;i++)
    {
        dp[1][i]=dp[2][i-1];
        dp[2][i]=dp[2][i-1]+dp[3][i-1]+dp[8][i-1];
        dp[3][i]=dp[1][i-1];
        dp[4][i]=dp[5][i-1]+dp[1][i-1];
        dp[5][i]=dp[10][i-1]+dp[4][i-1];
        dp[6][i]=dp[10][i-1];
        dp[7][i]=dp[8][i-1];
        dp[8][i]=dp[7][i-1];
        dp[9][i]=dp[7][i-1]+dp[6][i-1]+dp[9][i-1];
        dp[10][i]=dp[9][i-1];
        //for(j=1;j<=10;j++)
            //dp[j][i]=dp[j][i]%mod;
    }
    if(n==1)
        fout<<1;
    else
    {
        for(i=1;i<=10;i++)
            s=(s%mod+dp[i][n]%mod)%mod;
        fout<<s;
    }
    return 0;
}