const f:array[1..9] of byte = (1,1,2,3,5,8,13,21,34);
      modd = 666013;
var be,ki:text;
    n:longint;

function fib(n:qword):qword;
var np2m1,np2:qword;
begin
 if n < 10 then
   begin
    fib:=f[n];
    {write('fib ',n,' = ');
    writeln(fib);}
   end
  else
     begin
      np2:= fib(n div 2) mod modd;
      np2m1:= fib((n div 2)-1) mod modd;
      if odd(n) then
          begin
            fib := (np2m1 * (np2m1 + np2) + np2 * (2*np2 + np2m1)) mod modd;
            {write('fib ',n,' = ');
            writeln(fib);}
          end
         else
          begin
            fib := ( np2 * ( 2* np2m1 + np2 ) ) mod modd;
            {write('fib ',n,' = ');
            writeln(fib);}
          end;
     end;
end;

begin
 assign(be,'kfib.in');
 reset(be);
 assign(ki,'kfib.out');
 rewrite(ki);
 readln(be,n);
 {for n:=n downto 1 do writeln(ki,n,' : ',fib(n) mod modd);}
 writeln(ki,fib(n) mod modd);
 close(ki);
end.