program kfib;
const modulo=666013;
type mat=array[1..2,1..2]of qword;
var a,b,c:mat;
    i,j,n,k:longint;
    f,g:text;
function ab(a,b:mat):mat;
var c:mat;i,j,k:byte;  s:qword;
begin
fillchar(c,4,0);
for i:=1 to 2 do
 for j:=1 to 2 do
  begin
  s:=0;
  for k:=1 to 2 do s:=(s+((a[i,k] mod modulo)*(b[k,j]mod modulo))mod modulo)mod modulo;
  c[i,j]:=s;
  end;
ab:=c;
end;

function p(a:mat;n:integer):mat;
var i,j:byte;
begin
if n=1 then p:=a
       else p:=ab(p(a,n-1),a);
end;

begin
assign(f,'kfib.in');reset(f);
assign(g,'kfib.out');rewrite(g);
readln(f,k);
a[1,1]:=0;a[1,2]:=1; a[2,1]:=1; a[2,2]:=1;
b:=a;
for i:=1 to k-2 do b:=ab(b,a);
writeln(g,b[2,2]);
close(f);close(g);
end.