#include <iostream>
#include <fstream>
#include <math.h>
#define mod 1048576

using namespace std;

const char iname[] = "12perm.in";
const char oname[] = "12perm.out";

ifstream fin(iname);
ofstream fout(oname);

int i, sol, j, k, perm[11], N, viz[11], sol1, sol2, sol3, sol4, sol5, sol6;

void test()
{	
	int oki = 1;
	for(int j = 1; j < i; j ++)
		if(abs(perm[j] - perm[j + 1]) >= 3)
			oki = 0;
	if(oki)
		++sol;
}
		

void brut(int pas)
{
	if(pas == i + 1)
		test();
	else
	{
		for(int j = 1; j <= i; j ++)
		{
			if(!viz[j])
			{
				viz[j] = 1;
				perm[pas] = j;
				brut(pas + 1);
				viz[j] = 0;
			}
		}
	}
}
	
int solve(int n)
{	
	int i;
	for(i = 5; i <= n; i ++)
	{
		sol5 = (sol4 + sol2 + 2 * (i - 2)) % mod;
		sol2 = sol3;
		sol3 = sol4;
		sol4 = sol5 % mod;
	}
	return sol5;
}


int var1 = 1, var2 = 2, var3 = 6, var4 = 12, var5 = 20;
int main() 
{	
	/* brut
	for(i = 1; i <= 10; i ++)
	{	
		memset(perm, 0, sizeof(perm));
		memset(viz, 0, sizeof(viz));
		sol = 0;
		brut(1);
		fout << sol << "\n";
	}
	*/
	
	fin >> N;
	if(N == 1)
		fout << "1";
	else
		if(N == 2)
			fout << "2";
		else
			if(N == 3)
				fout <<"6";
			else
				if(N == 4)
					fout << "12";
				else
					if(N == 5)
						fout << "20";
					else
						fout << solve(N);
	return 0;
}