program fibo;
const fi='kfib.in';
      fo='kfib.out';
tr=666013;
type vector=array[1..2,1..2] of longint;
var a:array[1..2,1..2] of longint=((0,1),(1,1));
rez:array[1..2,1..2] of longint=((1,0),(0,1));
n,i,j,k,l,t: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;
  a:=c;
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,1]);
    close(f);
    close(g);
    end.