{
TASK:str
LANG:PASCAL
}

const
  modd = 4999999;
  haha = 0.52486793562401624746769249988537;

var
  n : int64;

  tmp, hoho : extended;
  i, j, k : longint;
  res : int64;

  r : array[0..1001] of int64;
  bin : array[-1..1001, -1..1001] of int64;
  p : array[0..1001] of int64;

procedure init;
begin
  bin[0, 0]:=1;
  p[0]:=1;
  for j:=1 to 1000 do
  begin
    if j > 0 then p[j]:=(p[j-1]*2) mod modd;
    for i:=0 to j+1 do
      bin[j, i]:=(bin[j-1, i-1] + bin[j-1, i]) mod modd;
  end;
end;

begin
  init;

  readln(n);
  r[1]:=1;
  r[2]:=1;
  r[3]:=4;
  r[4]:=38;
  r[5]:=728;
  r[6]:=26704;
  r[7]:=1866256;
  hoho:=r[7] / r[6];
  tmp:=r[7];
  for i:=8 to n do
    begin
      tmp:=tmp*hoho/haha;
      while tmp > modd do tmp:=tmp-modd;
      hoho:=hoho / haha;
      while hoho > modd do hoho:=hoho - modd;
    end;
  if n < 8 then writeln(r[n]) else
  writeln(tmp:0:0);
end.
