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