program fibonacci;

var n:longint;

function fib(n:longint):int64;
var pFib,cFib,nFib:int64;
    i:longint;
begin
pFib:=0;
cFib:=1;
if n=1 then fib:=1;
if n=0 then fib:=0
       else
        for i:=1 to n-1 do
         begin
          nFib:=pFib+cFib;
          pFib:=cFib;
          cFib:=nFib;
          fib:=cFib;
          if pFib>=666013 then pFib:=pFib mod 666013;
          if fib>=666013 then
           begin
            fib:=fib mod 666013;
            cFib:=cFib mod 666013;
            nFib:=nFib mod 666013;
           end;
        end;
end;

begin
assign(input,'kfib.in'); reset(input);
assign(output,'kfib.out'); rewrite(output);
read(n);
write(fib(n));
close(output);
end.