#include <iostream>
#include <fstream>

using namespace std;

int N;

int main(int argc, char *argv[]) {
	ifstream fin("12perm.in");
	fin >> N;
	fin.close();

	int A[4] = {12, 1, 2, 6};
	for (int i = 5; i <= N; ++i) 
		A[i % 4] = (A[(i + 1) % 4] + A[(i + 3) % 4] + 2*(i-2)) & (1048575);

	ofstream fout("12perm.out");
	fout << A[N % 4] << endl;
	fout.close();

	return 0;
}