#include <stdio.h>
#define N 1048576
int n;
int t[5];
int main()
{
	freopen("12perm.in","r",stdin);
	freopen("12perm.out","w",stdout);
	scanf("%d",&n);
	int i,x,a,b,c,d;
	if (n==1)
		printf("1\n");
	if (n==2)
		printf("2\n");
	if (n==3)
		printf("6\n");
	if (n==4)
		printf("12\n");
	a=1;
	b=2;
	c=6;
	d=12;
	if (n>=5)
	{
		for (i=5; i<=n; i++)
		{
			x=d+b+2*(i-2);
			if (x>N)
				x%=N;
			a=b;
			b=c;
			c=d;
			d=x;
		}
		printf("%d\n",x);
	}
	return 0;
}