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