#include<fstream>
using namespace std;
ifstream f("12perm.in");
ofstream g("12perm.out");
int n,v1=1,v2=2,v3=6,v4=12,v5;
int main()
{
	int i;
	f>>n;
	if(n==1)
		g<<v1;
	else
	if(n==2)
		g<<v2;
	else
	if(n==3)
		g<<v3;
	else
	if(n==4)
		g<<v4;
	else
	{
		for(i=5;i<=n;i++)
		{
			v5=(v4+v2+2*(i-2))%1048576;
			v2=v3;
			v3=v4;
			v4=v5;
		}
		g<<v4;
	}
	return 0;
}