program fibo;
const fi='kfib.in';
      fo='kfib.out';
tr=666013;
type vector=array[1..2,1..2] of int64;
var a:array[1..2,1..2] of int64=((0,1),(1,1));
rez:array[1..2,1..2] of int64=((1,0),(0,1));
n,t:int64;
i,j,k:longint;
f,g:Text;
procedure multime(var a,b:vector);
var c:vector=((0,0),(0,0));
begin
for i:=1 to 2 do
  for j:=1 to 2 do
     for k:=1 to 2 do
        c[i,j]:=(c[i,j]+(a[i,k]*b[k,j] mod tr))mod tr;
  for i:=1 to 2 do
  for j:=1 to 2 do
  a[i,j]:=c[i,j];
end;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
read(f,n);
while n>0 do
  begin
    if n mod 2=1 then
    multime(rez,a);
    multime(a,a);
    n:=n div 2;
    end;
    write(g,rez[1,2]);
    close(f);
    close(g);
    end.