type numar=array[0..1000000] of byte;
var fibonacci:array[1..350] of qword;
    BigNumberF,BigNumberS,BigNumberL,suma:numar;
    sum:qword;
    n,i,nmin:longint;

procedure initializare(var x:numar);
 begin
  fillchar(x,sizeof(x),0);
 end;


procedure adunare(x,y:numar; var z:numar);
var i:longint;
 begin
     for i:=1 to x[0] do z[i]:=z[i]+x[i]+y[i];
     for i:=1 to x[0]+y[0] do
     begin
      if z[i]>9 then
       begin
        z[i+1]:=z[i+1]+z[i] div 10;
        z[i]:=z[i] mod 10;
       end;
     end;
   for i:=x[0]+y[0] downto 1 do if z[i]<>0 then begin  z[0]:=i; break end;
 end;

procedure pathton(n:longint);
 begin
   fillchar(fibonacci,sizeof(fibonacci),0);
   fibonacci[1]:=1;
   fibonacci[2]:=1;
   for i:=3 to n do fibonacci[i]:=fibonacci[i-1]+fibonacci[i-2];
 end;

 procedure pathfromNToBigN();
 var fib1,fib2,sumak:string;
     c:0..1;
     i,j:longint;
 begin
 fib1:='';  sumak:='';
 fib2:='';
 initializare(BigNumberF);  initializare(BigNumberL); initializare(BigNumberS); Initializare(suma); //initializare cu 0-uri
 str(fibonacci[90],fib1);  //convertire fib(i-1),fib(i-2);
 str(fibonacci[89],fib2);  //>
 str(sum,sumak);
 //inserare numere initiale in vector
 Bignumberf[0]:=length(fib1);
  i:=length(fib1);
  j:=1;
  repeat
  val(fib1[i],bignumberf[j],c);
  dec(i);
  inc(j);
  until j=length(fib1)+1;

  Bignumbers[0]:=length(fib2);
  i:=length(fib2);
  j:=1;
  repeat
  val(fib2[i],bignumbers[j],c);
  dec(i);
  inc(j);
  until j=length(fib2)+1;

  //suma pana la 90
  suma[0]:=length(sumak);
  i:=length(sumak);
  j:=1;
  repeat
  val(sumak[i],suma[j],c);
  dec(i);
  inc(j);
  until j=length(sumak)+1;

  for i:=90 to n-1 do
   begin
    if BignumberF[0]>BignumberS[0] then adunare(BignumberF,BignumberS,bignumberl)
    else adunare(BignumberS,BignumberF,bignumberl);
    adunare(suma,bignumberL,suma);
    initializare(bignumbers);
    for j:=0 to bignumberf[0]+1 do
    bignumbers[j]:=bignumberf[j];
    initializare(bignumberf);
    for j:=0 to bignumberl[0]+1  do
    bignumberf[j]:=bignumberl[j];
    initializare(bignumberl);
   end;



 end;

begin
    assign(input,'kfib.in'); reset(input);
    assign(output,'kfib.out'); rewrite(output);
    readln(input,n);
    if n<90 then
    begin
      pathToN(n);
      sum:=0;
      //for i:=1 to n do sum:=sum+fibonacci[i];
      writeln(output,fibonacci[n] mod 666013);
      //Write(sum);
      exit
    end;
    if n>90 then
    begin
       nmin:=90;
       pathtoN(nmin);
       sum:=0;
       //for i:=1 to 90 do sum:=sum+fibonacci[i];
       pathfromNtoBigN;
       //for i:=suma[0] downto 1 do write(suma[i],' ');
       //writeln;
       for i:=bignumberf[0] downto 1 do write(output,bignumberf[i]);
      // writeln;
      // for i:=bignumbers[0] downto 1 do write(bignumbers[i],' ');
    end;
    close(input);
    close(output);
end.