Program kfibonacci;
var fi,fo : text;
    n,p : longint;
    a,b,c,rez:array[1..3,1..3] of qword;
procedure matrice;
begin
      a[1,1]:=(b[1,1]*c[1,1]+b[1,2]*c[2,1]) mod 666013;
      a[1,2]:=(b[1,1]*c[1,2]+b[1,2]*c[2,2]) mod 666013;
      a[2,1]:=a[1,2];
      a[2,2]:=(a[1,1]+a[1,2]) mod 666013;
end;

begin
     assign(fi,'kfib.in'); reset(fi); readln(fi,n); close(fi); assign(fo,'kfib.out');
     rewrite(fo);
     if n<3 then writeln(fo,'1')
            else begin
                 rez[1,1]:=0; rez[1,2]:=1; rez[2,1]:=1; rez[2,2]:=1;
                 n:=n-3;
                 while n>0 do begin
                              a[1,1]:=0; a[1,2]:=1; a[2,1]:=1; a[2,2]:=1;
                              p:=1;
                              while p*2<=n do  begin
                                               p:=p*2;
                                               b[1,1]:=a[1,1]; b[1,2]:=a[1,2]; b[2,1]:=a[2,1]; b[2,2]:=a[2,2];
                                               c[1,1]:=a[1,1]; c[1,2]:=a[1,2]; c[2,1]:=a[2,1]; c[2,2]:=a[2,2];
                                               matrice;
                                               end;
                              b[1,1]:=rez[1,1]; b[1,2]:=rez[1,2]; b[2,1]:=rez[2,1]; b[2,2]:=rez[2,2];
                              c[1,1]:=a[1,1]; c[1,2]:=a[1,2]; c[2,1]:=a[2,1]; c[2,2]:=a[2,2];
                              matrice;
                              rez[1,1]:=a[1,1]; rez[1,2]:=a[1,2]; rez[2,1]:=a[2,1]; rez[2,2]:=a[2,2];
                              n:=n-p;
                              end;
                 writeln(fo,(rez[2,1]+rez[2,2]) mod 666013);
                 end;
                 close(fo);
     end.