#include <stdio.h>

#define IN "12perm.in","r",stdin
#define OUT "12perm.out","w",stdout
#define Nmax 15000020 
#define MOD 1048576


int n,nrsol;
int sol[Nmax];

void citire()
{
	freopen(IN);
	scanf("%d",&n);
}
int valid(int k,int nr)
{
	for(int i=1;i<k;++i)
		if(sol[i]==nr)
			return 0;
	return 1;
}
void back(int k)
{
	if(k==n+1)
	{
		for(int i=1;i<=k;++i)
			if(sol[i]-sol[i+1]>3 || (-1)*(sol[i]-sol[i+1])>3)
				return;
	//	for(int i=1;i<=k;++i)
		//	printf("%d ",sol[i]);
		++nrsol;
		return;
	}
	for(int i=1;i<=n;++i)
		if(valid(k,i))
		{
			sol[k]=i;
			back(k+1);
		}
}
void afisare()
{
	freopen(OUT);
	printf("%d\n",nrsol%MOD);
}
int main()
{
	citire();
	back(1);
	afisare();
	return 0;
}