#include <iostream>

#define MAX_N 102400

using namespace std;

int Risultato[MAX_N]; // vettore che memorizza le soluzioni per ogni N
int N;

int calcola_ricorsivo_con_dinamica( int n ) // conto le possibilita' seguendo il procedimento
{
	if (n==0) {    // caso base: un modo di mettere 0 persone
		return 1;
	}
	if ( Risultato[n] > -1 ) { // se ho gia' calcolato il risultato lo restituisco senza farmi problemi
		return Risultato[n];
	}

	int count=0;              // se no lo calcolo ricorsivamente:
	for (int i=0; i<n; i++) { // conto i modi possibili, al variare della posizione i del piu' basso
		count = (count + calcola_ricorsivo_con_dinamica( i ) * calcola_ricorsivo_con_dinamica( n-i-1 )) % 1000000;
	}
	Risultato[n] = count;     // prima di uscire, salvo il risultato ottenuto
	return Risultato[n];
}

int main()
{
	cin >> N; // leggo l'input

	for (int i=0; i<=N; i++) { // inizializzo con un valore che indichi il non essere stati anora risolti
		Risultato[i] = -1;
	}

	cout << calcola_ricorsivo_con_dinamica(N) << endl; // stampo l'output
	return 0;
}