type matrice=array[1..2,1..2]of int64;

var rez,z,x,aux,m:matrice;
n:longint;

procedure inm(a,b:matrice;xa,ya,xb,yb:byte;var rezult:matrice);
var rez:matrice;  i,j,k:byte;
begin
fillchar(rez,sizeof(rez),0);
for i:=1 to xa do
    for j:=1 to yb do
        for k:=1 to xb do begin
        rez[i,j]:=(((a[i,k]*b[k,j])mod 666013)+rez[i,j])mod 666013;
        end;
rezult:=rez;
end;


procedure log(n:longint;var rezult:matrice);
begin
if n=1 then rezult:=z
       else if n mod 2=0 then begin
                         log(n div 2,x);
                         inm(x,x,2,2,2,2,aux);
                         rezult:=aux;
                         end
                         else begin
                              log(n-1,x);
                              inm(z,x,2,2,2,2,aux);
                              rezult:=aux;
                              end;
end;

begin
assign(input,'kfib.in');reset(input);
assign(output,'kfib.out');rewrite(output);
read(n);
z[1,1]:=0;z[1,2]:=1;z[2,1]:=1;z[2,2]:=1;
m[1,1]:=0;m[1,2]:=1;
if n>2 then begin
log(n-1,x);
inm(m,x,1,2,2,2,rez);
writeln(rez[1,2]);
end
else write(m[1,n]);
close(output);
end.