//Ilie Dumitru
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
const int NMAX=1505;
const int MOD=(1<<20)-1;
const int DIM=6;

struct mat
{
	long long int v[DIM][DIM];
};

mat I, A, X;

/*
101000
001010
000000
010000
101110
010001
*/

void init()
{
	int i, j;
	const int N=11;
	const int pi[N]={0, 0, 1, 1, 3, 4, 4, 4, 4, 5, 5};
	const int pj[N]={0, 2, 2, 4, 1, 0, 2, 3, 4, 1, 5};

	for(i=0;i<DIM;++i)
		for(j=0;j<DIM;++j)
			I.v[i][j]=(i==j), A.v[i][j]=X.v[i][j]=0;

	for(i=0;i<N;++i)
		A.v[pi[i]][pj[i]]=1;

	X.v[2][0]=2;
}

void mult(mat& ans, mat& a, mat& b)
{
	int i, j, k;

	for(i=0;i<DIM;++i)
		for(j=0;j<DIM;++j)
			for(k=ans.v[i][j]=0;k<DIM;++k)
				ans.v[i][j]=(ans.v[i][j]+a.v[i][k]*b.v[k][j])&MOD;
}

void fastExp(mat& ans, int p)
{
	if(p==0)
		ans=I;
	else if(p==1)
		ans=A;
	else
	{
		if(p&1)
		{
			mat aux, aux1;
			fastExp(aux, p>>1);
			mult(aux1, aux, aux);
			mult(ans, aux1, A);
		}
		else
		{
			mat aux;
			fastExp(aux, p>>1);
			mult(ans, aux, aux);
		}
	}
}

int getAns(mat& M)
{
	mult(I, M, X);
	return (I.v[0][0]+I.v[1][0]+I.v[2][0]+I.v[3][0]+I.v[4][0]+I.v[5][0])&MOD;
}

int main()
{
	FILE* f=fopen("12perm.in", "r"), *g=fopen("12perm.out", "w");
	int N;
	mat M;

	fscanf(f, "%d", &N);
	if(N==1)
		fprintf(g, "1\n");
	else
	{
		init();
		fastExp(M, N-2);
		fprintf(g, "%d\n", getAns(M));
	}

	fclose(f);
	fclose(g);
	return 0;
}