#include <bits/stdc++.h>
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
const int N=15e6+5,mod=1048576;
int n,i,j,s,d[N][7];
void init()
{
    for(i=1;i<=6;++i)
    {
        d[3][i]=1;
    }
    d[4][0]=2;
    d[4][1]=2;
    d[4][2]=1;
    d[4][3]=2;
    d[4][4]=1;
    d[4][5]=1;
    d[4][6]=1;
    d[4][7]=2;
}
int main()
{
    fin>>n;
    if(n==1) {fout<<1; return 0;}
    if(n==2) {fout<<2; return 0;}
    init();
    for(i=5;i<=n;++i)
    {
        d[i][0]=d[i-1][7]+d[i-1][1];
        d[i][7]=d[i-1][0]+d[i-1][3];
        d[i][1]=d[i-1][1]+d[i-1][6];
        d[i][2]=d[i-1][1];
        d[i][3]=d[i-1][3]+d[i-1][5];
        d[i][4]=d[i-1][3];
        d[i][5]=d[i-1][6];
        d[i][6]=d[i-1][5];
        for(j=0;j<=7;++j) d[i][j]%=mod;
    }
    for(i=0;i<=7;++i)
    {
        s+=d[n][i];
        s%=mod;
    }
    fout<<s;
    return 0;
}