#include <fstream>
#include <cstring>
using namespace std;

const int kMod = 1048576;

int N, ans;

int main() {
	ifstream("12perm.in") >> N;
	if (N < 4) {
		switch (N) {
			case 1:
			ans = 1;
			break;
			case 2:
			ans = 2;
			break;
			default:
			ans = 6;
		}
	} else {
		int d, d1 = 6, d2 = 2, d3 = 2;
		for (int i = 4; i <= N; ++i) {
			d = (d1 + d3 + 2 * (i - 2)) % kMod;
			d3 = d2;
			d2 = d1;
			d1 = d;
		}
		ans = d;
	}
	ofstream("12perm.out") << ans << "\n";
	return 0;
}