Program kfib;
 var f,g:text; k:longint;
 function A (x:longint):int64;
  begin
   if x=0 then exit (0);
   if x=1 then exit (1);
   if x=2 then exit (1);
   if odd (x)
     then A:=(sqr (A (x div 2))+sqr (A ((x+1) div 2))) mod 666013
     else A:=A (x div 2)*(A ((x div 2)-1)+A (x div 2+1)) mod 666013;
  end;
 begin
  assign (f,'kfib.in'); reset (f);
  assign (g,'kfib.out'); rewrite (g);
  readln (f,k);
  writeln (g,A (k));
  close (f); close (g);
 end.