program fibonaci;
  const modul=666013;
  var n,i:longint;
      a:array[1..3,0..30] of int64;
      d:array[0..30] of int64;
      an,an2:array[1..3]of int64;

begin
  assign(input,'kfib.in');
  reset(input);
  assign(output,'kfib.out');
  rewrite(output);
  a[1,0]:=0;
  a[2,0]:=1;
  a[3,0]:=1;
  for i:=1 to 30 do
    begin
      a[1,i]:=(sqr(a[1,i-1])+sqr(a[2,i-1]))mod modul;
      a[2,i]:=((a[1,i-1]+a[3,i-1])*a[2,i-1]) mod modul;
      a[3,i]:=(sqr(a[3,i-1])+sqr(a[2,i-1]))mod modul;
    end;
 d[0]:=1;
 for i:=1 to 30 do d[i]:=d[i-1]*2;
 readln(n);
 n:=n-2;
 an[1]:=1;an[2]:=0;an[3]:=1;
 for i:=30 downto 0 do
   begin
     while n>=d[i] do
       begin
         an2[1]:=(an[1]*a[1,i]+an[2]*a[2,i])mod modul;
         an2[2]:=(an[1]*a[2,i]+an[2]*a[3,i])mod modul;
         an2[3]:=(an[2]*a[2,i]+an[3]*a[3,i])mod modul;
         an:=an2;
         n:=n-d[i];
       end;
   end;
 writeln((an[3]+an[2])mod modul);
 close(input);close(output);
end.