#include<fstream>
#include<cstring>
#define mod 1048576
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
int n,a,b,d[2][7],sol,i,j;
int main(){
    fin>>n;
    if(n==1||n==2){fout<<n; return 0;}
    d[1][1]=2;
    d[1][5]=2;
    d[1][6]=2;
    a=1;
    for(i=4;i<=n;i++)
    {a=i%2;b=1-a;
        d[a][1]=d[b][1];
        d[a][2]=d[b][3]+d[b][6];
        d[a][4]=d[b][4]+d[b][6];
        d[a][5]=d[b][1]+d[b][5]+d[b][2];
        d[a][6]=d[b][5];
        for(j=1;j<=6;j++) if(d[a][j]>mod) d[a][j]-=mod;
        if(d[a][5]>mod) d[a][5]-=mod;
    }
    for(j=1;j<=6;j++)
        sol=(sol+d[a][j])%mod;
    fout<<sol;
    return 0;
}