#include <fstream>

using namespace std;

ifstream f("dirichlet.in");
ofstream g("dirichlet.out");

const int MOD = 9999991;

int n, rez;
long long D[2];

int main()
{
	f >> n;
	if (n < 3)
		rez = n;
	else {
		int l = 1;
		D[0] = 2;
		for (int i = 3; i <= n; i++) {
			D[l] = ((i - 1) * D[l ^ 1] + 1) % MOD;
			l ^= 1;
		}
		rez = D[l ^ 1];
	}
	
	g << rez << '\n';
	
	return 0;
}