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