# include <fstream>

using namespace std;

# define input "12perm.in"
# define output "12perm.out"

long a,b,c,d,e,n,i,aux;

int main ()
{
	ifstream fin ( input ) ;
	ofstream fout ( output ) ;

	fin >> n;

	if(n == 1)
	{
		fout << 1;
		return 0;
	}
	if(n == 2)
	{
	   fout<< 2;
		return 0;
	}
	if(n == 3)
	{
		fout << 6;
		return 0;
	}
	if(n == 4)
	{
		fout << 12;
		return 0;
	}
	if(n == 5)
	{
		fout << 20;
		return 0;
	}
	if(n == 6)
	{
		fout << 34;
		return 0;
	}

	a = 34;
	b = 22;
	c = 10;
	d = 8;
	e = 6;

	for(i = 7;i<=n;i++)
	{
		a +=b;
		b +=c;
		aux = c;
		c += e;
		e = d;
		d = aux;

		a%=1048576;
		b%=1048576;
		c%=1048576;
		d%=1048576;
		e%=1048576;
	}

	fout << a;

	return 0;
}