{** Муниципальная ОИ-2014. Задача "ТРАФАРЕТЫ" **}
{** Решение Киндер М.И.                       **}
const mmod = 1000000009;
var i, n, k : integer;
          M : array[0..3000] of int64;
{***********************************************}
begin
  assign(input, 'input.txt'); reset(input);
  assign(output,'output.txt');rewrite(output);
  read(input, n);
  close(input);
  M[0]:= 1;
  for i:= 1 to n do begin M[i]:= M[i-1] mod mmod;
      for k:= 1 to i-1 do
          M[i]:= (M[i] + M[k-1] * M[i-1-k]) mod mmod;
  end;
  writeln(M[n]);
  close(output);
end.

