Program kfib;
const md=666013;
type tip=array [1..2,1..2] of int64;
 var a,s:tip;
     k,i,j:longint;
     fi,fo:text;
procedure inmulteste(var a:tip; b:tip);
var aux:tip;
begin
 aux[1,1]:=(((a[1,1]*b[1,1]) mod md)+((a[1,2]*b[2,1]) mod md)) mod md;
 aux[1,2]:=(((a[1,1]*b[1,2]) mod md)+((a[1,2]*b[2,2]) mod md)) mod md;
 aux[2,1]:=(((a[2,1]*b[1,1]) mod md)+((a[2,2]*b[2,1]) mod md)) mod md;
 aux[2,2]:=(((a[2,1]*b[1,2]) mod md)+((a[2,2]*b[2,2]) mod md)) mod md;
 a[1]:=aux[1]; a[2]:=aux[2];
end;
procedure pow(t:longint);
 begin
  while t>0 do
   if t mod 2=0 then begin
                      inmulteste(a,a);
                      t:=t div 2;
                      end
   else begin
          inmulteste(s,a);
           t:=t-1;
           end;
 end;
begin
 assign(fi,'kfib.in');
  assign(fo,'kfib.out');
 reset(fi); rewrite(fo);
 readln(fi,k);
 a[1,1]:=0; a[1,2]:=1; a[2,1]:=1; a[2,2]:=1; s[2]:=a[2]; s[1]:=s[2];
  pow(k-1);
 write(fo,s[2,1]);
close(fo);
end.