#include <stdio.h>

/*
0 -> 0
1 -> 2
2 -> 2 si 3
3 -> 0 si 1
4 -> 1 si 2
*/

#define MOD 1048576
int type[5];
int main()
{
    int n, i, j, b, c, d, e;
    FILE *fi=fopen("12perm.in", "r"), *fo=fopen("12perm.out", "w");
    fscanf(fi, "%d", &n);
    type[0]=type[1]=type[4]=type[3]=2;
    type[2]=4;
    for(i=4;i<n;i++){
        b=type[1];
        c=type[2];
        d=type[3];
        e=type[4];
	type[1]=0;
	type[3]=0;
	type[4]=0;
        //1
	type[2]+=b;
	//2
	type[3]+=c;
	//3
	type[0]+=d;
	type[1]+=d;
	//4
	type[1]+=e;
	type[2]+=e;
        for(j=0;j<5;j++)
            if(type[j]>MOD)
                type[j]%=MOD;
    }
    fprintf(fo, "%d\n", (type[0]+type[1]+type[2]+type[3]+type[4])%MOD);
    fclose(fi);
    fclose(fo);
    return 0;
}