#include <fstream>
#define mod 666013

using namespace std ;

ifstream f ("kfib.in") ;
ofstream g ("kfib.out") ;

int k ;
long long S[3][3] ; //va fi matricea solutia
long long A[3][3] ; //va fi asa-zisa matrice Z , cea care ajuta la recurenta
long long C[3][3] ; //va fi o matrice intermediara

void solve () ;

int main ()
{
 f >> k ;
 solve () ;
}

void solve ()
{
 //initializam matricea S cu primii doi termeni ai recurentei , si matricea A cu forma ei generala
 A[0][0] = 0 ;
 A[0][1] = A[1][0] = A[1][1] = 1 ;
 S[0][0] = 0 ; S[0][1] = 1 ;
 --k ; //scadem un k deoarece suntem la f1 in s[0][1]
 for ( ; k ; k /= 2 ) // in timp logaritmic ( tot injumatatim pe k )
    {
     if ( k % 2 == 1 ) //daca e impar facem a^n = a^(n-1)*a
        {
         //in cazul nostru inmultim odata S cu A si o pastram initial in C ca mai apoi sa o mutam inapoi in S
         for ( int i = 0 ; i <= 1 ; ++i )
            for ( int j = 0 ; j <= 1 ; ++j )
                {
                 C[i][j] = 0 ;
                 for ( int l = 0 ; l <= 1 ; ++l )
                    C[i][j] = ( C[i][j] + S[i][l] * A[l][j] ) % mod ;
                }
         for ( int i = 0 ; i <= 1 ; ++i )
            for ( int j = 0 ; j <= 1 ; ++j )
                S[i][j] = C[i][j] ;
        }
     //nu are rost sa-l scadem pe k deoarece la injumatatire intreaga , tot acolo vine
     //acum consideram operatia pt par : a^n=(a^(n/2)^2
     //in cazul nostru inmultim matricea de ajutor la recurenta A cu ea insasi , tinand-o partial in C si reatribuind-o in A
     for ( int i = 0 ; i <= 1 ; ++i )
        for ( int j = 0 ; j <= 1 ; ++j )
            {
             C[i][j] = 0 ;
             for ( int l = 0 ; l <= 1 ; ++l )
                C[i][j] = ( C[i][j] + A[i][l] * A[l][j] ) % mod ;
            }
     for ( int i = 0 ; i <= 1 ; ++i )
        for ( int j = 0 ; j <= 1 ; ++j )
            A[i][j] = C[i][j] ;
    }
 //afisam solutia care se afla in Fn
 g << S[0][1] ;
}