#include <iostream>
#include <fstream>


using namespace std;

ifstream f ("kfib.in") ;

ofstream g ("kfib.out") ;

unsigned long long K  ;

struct matrice {

    unsigned long a , b , c , d  ;

};

matrice inmultire (  matrice X , matrice Y )

{ matrice Z ;

unsigned long p = 666013 ;

Z.a = (X.a * Y.a + X.b * Y.c)%p ;

Z.b = (X.a * Y.b + X.b * Y.d)%p ;

Z.c = (X.c * Y.a + X.d * Y.c)%p ;

Z.d = (X.c * Y.b + X.d * Y.d)%p ;

return Z ;

}


matrice putere ( matrice X , unsigned long n)

{  matrice A ;

    if ( n% 2==0) {  A = putere(X ,n/2)    ; return inmultire (A , A)  ; }


    else {  A= putere (X , n/2) ; A = inmultire (A , A)  ; return inmultire (A , X)  ; }

}






int main()
{ f >> K ;

matrice Fibo ;

Fibo.a = 0 ; Fibo.b = 1 ; Fibo.c = 1 ; Fibo.d = 1 ;


 Fibo = putere ( Fibo  , K - 1) ;

 g << Fibo.d ;


    return 0;
}