{
Stiind ca p(n)=p(n-1)+p(n-2) =>

|1 1| * |p(n-1)| = | p(n)  |
|1 0|   |p(n-2)|   | p(n-1)|

  unde |w x| este o matrice 2x2 cu elementele w, x, y si z,
       |y z|
  iar | x | este o matrice 2x1 cu elementerele x si y
      | y |

=>
| p(n)  |=|1 1| * |1 1| * |p(n-2)|
| p(n-1)| |1 0|   |1 0|   |p(n-3)|

adica (pentru ca inmultirea matricilor este asociativa):
| p(n)  |=( |1 1| ^ 2 )* |p(n-2)|
| p(n-1)| ( |1 0|     )  |p(n-3)|

unde (|w x| ^ 2) este o matrice 2x2 cu elementele w, x, y si z ridicata la
     (|y z|    )    puterea a 2-a


=> prin inductie matematica
| p(n)  |=(|1 1| ^ (n-2)) * |p(2)|
| p(n-1)| (|1 0|        )   |p(1)|

adica

| p(n)  |=(|1 1| ^ (n-2)) * |1|
| p(n-1)| (|1 0|        )   |1|

de unde se poate afla p(n); ce ramane de calculat este de ridicat
matricea |1 1| la puterea n-2 (in timp logaritimic)
         |1 0|
}
type matrice=array[1..2,1..2]of int64;
const modnr=666013;
      i:matrice=((1,1),(1,0));
var k:longint;

function inmultire(i,j:matrice):matrice;
begin
inmultire[1,1]:=((i[1,1]*j[1,1])mod modnr+(i[1,2]*j[2,1])mod modnr)mod modnr;
inmultire[1,2]:=((i[1,1]*j[1,2])mod modnr+(i[1,2]*j[2,2])mod modnr)mod modnr;
inmultire[2,1]:=((i[2,1]*j[1,1])mod modnr+(i[2,2]*j[2,1])mod modnr)mod modnr;
inmultire[2,2]:=((i[2,1]*j[1,2])mod modnr+(i[2,2]*j[2,2])mod modnr)mod modnr;
end;

function lgput(k:longint):matrice;
var j:matrice;
begin
if k=1 then lgput:=i
       else begin
            j:=lgput(k shr 1);
            j:=inmultire(j,j);
            if k and 1=0 then lgput:=j
                         else lgput:=inmultire(i,j);
            end;
end;

begin
assign(input,'kfib.in');
reset(input);
read(k);
assign(output,'kfib.out');
rewrite(output);
if k<3 then writeln('1')
       else begin
            i:=lgput(k-2);
            writeln((i[1,1]+i[1,2])mod modnr);
            end;
close(output);
close(input);
end.