#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("12perm.in");
ofstream fout ("12perm.out");

int rez = 0,n,Last[6];
const int mod = 1048576;

int main() {
	
	fin >> n;
	if ( n == 1)
		fout <<	1;
	else
		if ( n == 2)
			fout << 2;
		else
			if ( n == 3)
				fout << 6;
			else
				if ( n == 4)
					fout << 12;
	else{ 
	Last[1] = 12;
	Last[2] = 6;
	Last[3] = 2;
	for ( int i = 5; i <= n; ++i) {
		rez = (Last[1] + Last[3] +  2 * ( i - 2)) % mod;
		Last[3] = Last[2];
		Last[2] = Last[1];
		Last[1] = rez;
	}
	fout << Last[1];
}
}