const   fin = 'kfib.in'; fout = 'kfib.out'; m = 666013;

type
        matrice = array[1..2,1..2] of qword;
var
        f : matrice;

procedure fibo( n : longword );
begin
        if (n > 1) then
        begin
                fibo( n div 2 );
                f[2][1] := (f[2][1] * f[1][1] + f[2][1] * f[2][2]) mod m;
                f[2][2] := (sqr(f[1][2]) + sqr(f[2][2])) mod m;
                f[1][1] := (sqr(f[1][1]) + sqr(f[1][2])) mod m;
                f[1][2] := f[2][1];
                if (n mod 2 = 1) then
                begin
                        f[1][1] := f[1][2];
                        f[1][2] := f[2][2];
                        f[2][2] := (f[2][1] + f[2][2]) mod m;
                        f[2][1] := f[1][2];
                end;
        end;
end;

procedure main();
var
        n : longword;
begin
        assign( input, fin ); reset( input );
        assign( output, fout ); rewrite( output );

        f[1][2] := 1;
        f[2][1] := 1;
        f[2][2] := 1;

        readln( n );

        fibo( n + 1 );

        write( f[1][1] ,#10 );
end;

begin
        main();
end.