type matr=array[1..3,1..3] of int64;
var n:longint;
    qq:matr;
procedure produs(var a,b:matr);
var aux:matr;
    i,k,j:longint;
begin
  for i:=1 to 2 do
      for k:=1 to 2 do
        begin
            aux[i,k]:=0;
            for j:=1 to 2 do
                aux[i,k]:=(aux[i,k]+a[i,j]*b[j,k] mod 666013) mod 666013;
      end;
  for i:=1 to 2 do
      for j:=1 to 2 do
        a[i,j]:=aux[i,j];
end;
procedure putere(var a:matr; n:longint);
var p:matr;
    i,j:longint;
begin
  p[1,1]:=1;
  p[2,2]:=1;
  p[2,1]:=0;
  p[1,2]:=0;
  while n<>0 do
    begin
      if n mod 2=1 then
         produs(p,a);
      produs(a,a);
      n:=n div 2;
    end;
  for i:=1 to 2 do
    for j:=1 to 2 do
       a[i,j]:=p[i,j];
end;
begin
  assign(input,'kfib.in');
  assign(output,'kfib.out');
  reset(input);
  rewrite(output);
  readln(n);
  qq[1,1]:=1;
  qq[1,2]:=1;
  qq[2,1]:=1;
  qq[2,2]:=0;
  putere(qq,n);
  writeln(qq[2,1]);
  close(output);
end.