var n,i:int64;
    j,p:array[1..3,1..3] of int64;
    
procedure inmmatr;
var m:array[1..3,1..3] of longint;
begin
  m[1,1]:=j[1,1]*j[1,1]+j[1,2]*j[2,1];
  m[1,2]:=j[1,1]*j[1,2]+j[1,2]*j[2,2];
  m[2,1]:=j[2,1]*j[1,1]+j[2,2]*j[2,1];
  m[2,2]:=j[2,1]*j[1,2]+j[2,2]*j[2,2];
  j[1,1]:=m[1,1];
  j[1,2]:=m[1,2];
  j[2,1]:=m[2,1];
  j[2,2]:=m[2,2];
end;

procedure inmmatr2;
var m:array[1..3,1..3] of longint;
begin
  m[1,1]:=j[1,1]*p[1,1]+j[1,2]*p[2,1];
  m[1,2]:=j[1,1]*p[1,2]+j[1,2]*p[2,2];
  m[2,1]:=j[2,1]*p[1,1]+j[2,2]*p[2,1];
  m[2,2]:=j[2,1]*p[1,2]+j[2,2]*p[2,2];
  p[1,1]:=m[1,1] mod 666013;
  p[1,2]:=m[1,2] mod 666013;
  p[2,1]:=m[2,1] mod 666013;
  p[2,2]:=m[2,2] mod 666013;
end;
    
begin
  assign(input,'kfib.in');
  assign(output,'kfib.out');
  reset(input);
  rewrite(output);
  read(n);
  p[1,1]:=0;
  p[1,2]:=1;
  p[2,1]:=1;
  p[2,2]:=1;
  dec(n,2);
  while n>0 do begin
    i:=1;
    j[1,1]:=0;
    j[1,2]:=1;
    j[2,1]:=1;
    j[2,2]:=1;
    while i*2<=n do begin
      inmmatr;
      i:=i*2;
    end;
    n:=n-i;
    inmmatr2;
  end;
  write(p[2,2]);
end.