#include <stdio.h>
#define MOD 1048576

int main()
{
	int n, i;
	int t[] = {0, 1, 2, 6, 12};
	freopen("12perm.in", "r", stdin);
	freopen("12perm.out", "w", stdout);

	scanf("%d\n", &n);

	for(i = 5; i <= n; ++i)
	{
		t[i] = t[i-1] + t[i-3] + 2*(i-1);

		t[i] = t[i-1];
		t[i-1] = t[i-2];
		t[i-2] = t[i-3];

		if(t[i] >= MOD)
			t[i] %= MOD;
	}

	if(n > 4)
		printf("%d\n", t[i]%MOD);
	else
		printf("%d\n", t[n]);

	fclose(stdin);
	fclose(stdout);

	return 0;
}