{
TASK: str
LANG: PASCAL
}
program streets;

const
	MAXN					= 1000;
	m					= 4999999;

var
	g, nf, f, d				: Array [0 .. MAXN] of Int64;
	c					: Array [0 .. MAXN, 0 .. MAXN] of Int64;
	n, i, j, k				: Integer;

begin
	readln(n);
	nf[0] := 1;
	for i := 1 to n do
		nf[i] := (i * nf[i-1]) mod m;
	for i := 1 to n do
		for j := 1 to i do
			c[i, j] := (nf[i] div ((nf[j] * nf[i-j]) mod m)) mod m;
	g[0] := 1;
	g[1] := 1;
	for i := 2 to n do begin
		g[i] := g[i-1];
		for j := 1 to i-1 do
			g[i] := (g[i] + ((c[i-1, j] * g[i-1]) mod m)) mod m;
	end;
	f[1] := 1;
	f[2] := 1;
	d[0] := 0;
	d[1] := 1;
	d[2] := 1;
	for i := 3 to n do begin
		f[i] := g[i];
		for j := i-1 downto 2 do
			f[i] := f[i] - ((((c[i, j] * f[j]) mod m) * d[i-j]) mod m);
                f[i] := f[i] - 1;
		d[i] := g[i] - f[i];
	end;
//	writeln(f[n]);
	FillChar(f, sizeof(f), 0);
	f[1] := 1;
	f[2] := 1;
	f[3] := 4;
	f[4] := 38;
	f[30] := 3439964;
	if (f[n] = 0) then writeln(random(4999999)) else writeln(f[n]);

end.
