Program kfib;
 var f,g:text; a:array[1..2,1..2]of int64;
     k:longint;
 procedure a1;
  begin
   a[1,2]:=a[1,2]*(a[1,1]+a[2,2]) mod 666013;
   a[1,1]:=(sqr (a[1,1])+sqr (a[2,1])) mod 666013;
   a[2,2]:=(sqr (a[2,2])+sqr (a[2,1])) mod 666013;
   a[2,1]:=a[1,2];
  end;
 procedure a2;
  begin
   a[1,1]:=a[2,1];
   a[2,1]:=a[2,2];
   a[2,2]:=(a[1,1]+a[2,1]) mod 666013;
   a[1,2]:=a[2,1];
  end;
 procedure putere (x:longint);
  begin
   if x>1 then begin
     putere (x div 2); a1;
     if odd (x) then a2;
   end;
  end;
 begin
  assign (f,'kfib.in'); reset (f);
  assign (g,'kfib.out'); rewrite (g);
  readln (f,k);
  a[1,2]:=1; a[2,1]:=1; a[2,2]:=1;
  putere (k+1);
  writeln (g,a[1,1]);
  close (f); close (g);
 end.