const modulo=666013;
var a,rs,aux:array[1..2,1..2] of qword;
    k:longint;
begin
assign(input,'kfib.in');
assign(output,'kfib.out');
reset(input);
rewrite(output);
 readln(k);
    a[1][1]:=0; a[1][2]:=1; a[2][1]:=1; a[2][2]:=1;
    rs[1][1]:=0; rs[1][2]:=1; rs[2][1]:=1; rs[2][2]:=1;

    dec(k);
    while k>0 do
      if k mod 2=0 then begin
                         aux[1][1]:=(((a[1][1]*a[1][1]) mod modulo)+((a[1][2]*a[2][1]) mod modulo)) mod modulo;
                         aux[1][2]:=(((a[1][1]*a[1][2]) mod modulo)+((a[1][2]*a[2][2]) mod modulo)) mod modulo;
                         aux[2][1]:=(((a[2][1]*a[1][1]) mod modulo)+((a[2][2]*a[2][1]) mod modulo)) mod modulo;
                         aux[2][2]:=(((a[2][1]*a[1][2]) mod modulo)+((a[2][2]*a[2][2]) mod modulo)) mod modulo;
                         a[1][1]:=aux[1][1]; a[2][1]:=aux[2][1]; a[1][2]:=aux[1][2]; a[2][2]:=aux[2][2];
                         k:=k div 2;
                        end
                   else begin
                         aux[1][1]:=(((rs[1][1]*a[1][1]) mod modulo)+((rs[1][2]*a[2][1]) mod modulo)) mod modulo;
                         aux[1][2]:=(((rs[1][1]*a[1][2]) mod modulo)+((rs[1][2]*a[2][2]) mod modulo)) mod modulo;
                         aux[2][1]:=(((rs[2][1]*a[1][1]) mod modulo)+((rs[2][2]*a[2][1]) mod modulo)) mod modulo;
                         aux[2][2]:=(((rs[2][1]*a[1][2]) mod modulo)+((rs[2][2]*a[2][2]) mod modulo)) mod modulo;
                         rs[1][1]:=aux[1][1]; rs[2][1]:=aux[2][1]; rs[1][2]:=aux[1][2]; rs[2][2]:=aux[2][2];
                         dec(k);
                        end;

           writeln(rs[2][1]);

close(input);
close(output);
{Totusi este trist in lume}
end.