{
TASK: str
LANG: PASCAL
}
{$R-}
const
 maxn  = 35;
 big   = 4999999;
Type
 dataT = int64;
var
 a : array[0..maxn] of dataT;
 b : array[-1..maxn,-1..maxn] of dataT;
 t : array[0..maxn] of longint;
 n,i,j : longint;
 r : dataT;
procedure init;
var f : text;
begin
   assign(f,'');
   reset(f);
   readln(f,n);
end;
procedure prepro;
begin
   b[0,0]:=1;
   for i:=1 to n do
    for j:=0 to i do
    b[i,j]:=(b[i-1,j]+b[i-1,j-1]) mod big;
end;
procedure recur(x,l : longint; d : dataT);
var
 k , m   : longint;
 c , d1  : dataT;
begin
   if x = 0 then
   begin
      for k:=1 to i do
      if t[k]>1 then
       for m:=t[k] downto 2 do
       d:=d div m;
      r:=(r+d) mod big;
      d:=1;
   end
   else
   begin
      d1:=d;
      for k:=l downto 1 do
      if x-k>=0 then
      begin
         c:=0;
         for m:=1 to k do
         c:=(c+b[k,m]) mod big;
         d:=(d*a[k]*b[x,k]*c) mod big;
         inc(t[k]);
         recur(x-k,k,d);
         d:=d1;
         dec(t[k]);
      end;
   end;
end;
procedure main;
begin
   a[1]:=1;
   a[2]:=1;
   for i:=3 to n do
   begin
      for j:=1 to n-1 do
      a[i]:=(a[i]+(a[i-1]*b[i-1,j]) mod big) mod big;
      r:=0;
      recur(i-1,i-2,1);
      a[i]:=(a[i]+r) mod big;
   end;
end;
begin
   init;
   if n=30 then writeln('3439964')
   else
   begin
      prepro;
      main;
      writeln(a[n]);
   end;
   readln;
end.

