{
TASK: str
LANG: PASCAL
}
const
 maxn = 50;
 big  = 4999999;
var
 a : array[0..maxn] of longint;
 b : array[0..maxn,0..maxn] of longint;
 t : array[0..maxn] of longint;
 n,i,j,d,r : longint;
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, d : longint);
var
 k , m , c , d1  : longint;
begin
   if x = 0 then
   begin
      for k:=1 to n 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;
      d:=1;
      r:=0;
      recur(i-1,i-2,1);
      a[i]:=(a[i]+r) mod big;
   end;
end;
begin
   init;
   prepro;
   main;
   writeln(a[n]);
end.