#include<stdio.h>
const char in[]="12perm.in", out[]="12perm.out";
const int mod = 1048576;
int sol,t1 = 1, t2 = 2, t3 = 6, t4 = 12, n , j = 5, last, aux;
int main()
	{
	freopen(in,"r",stdin);
	freopen(out,"w",stdout);
		scanf("%d", &n);
		for(; j <= n ; ++j)
		{
			aux = t4;
			t4 = t3 + t1 + 2 * ( j - 2 );
			if(t4 > mod) t4 -= mod;
			t1 = t2; t2 = t3; t3 = aux;
		}
		printf("%d\n", t4);
		return 0;
}