var i,j,f1,f2,f3:integer;
    fin,fout:text;
begin
assign(fin,'dirichlet.in');
reset(fin);
assign(fout,'dirichlet.out');
rewrite(fout);
readln(fin,j);
f1:=1; i:=3;
f2:=1;
while i<=(j*2)-1 do
 begin
   f3:=f1+f2;
   f1:=f2;
   f2:=f3;
   inc(i);
  end;
writeln(fout,f2 mod 9999991);
close(fin); close(fout);
end.