#include <cstdio>
#include <cstdlib>

#define mod  666013

long long K , p ;
long long Z [ 3 ][ 3 ] , rez [ 3 ][ 3 ] , aux [ 3 ][ 3 ] ;
void citire ()
{
    FILE *fin ;
    fin = fopen ( "kfib.in" , "rt" ) ;

    fscanf ( fin , "%lld" , &K ) ;
    fclose ( fin ) ;

}

void copy ( long long A [  ][ 3 ] , long long B [  ][ 3 ] )
{
    for ( int i = 0 ; i <= 1 ; i++ )
        for ( int j = 0 ; j <= 1 ; j++ )
            A [ i ][ j ] = B [ i ][ j ] ;
}

void mult ( long long A[  ][ 3 ] , long long B [  ][ 3 ] , long long C [  ][ 3 ] )
{
    for ( int i = 0 ; i <= 1 ; i++ )
        for ( int j = 0 ; j <= 1 ; j++ )
            A [ i ][ j ] = 0 ;

    for ( int i = 0 ; i <= 1 ; i++  )
        for ( int j = 0 ; j <= 1 ; j++ )
            for ( int k = 0 ; k <= 1 ; k++ )
                    A [ i ][ j ] = ( A[ i ][ j ] + ( B [ i ][ k ] * C [ k ][ j ] ) % mod ) % mod ;

}
void add ( long long A [  ][ 3 ] , long long B [  ][ 3 ] )
{
    for ( int i = 0 ; i <= 1 ; i++ )
        for ( int j = 0 ; j <= 1 ; j++ )
            A [ i ][ j ] =A [ i ][ j ] + B [ i ][ j ] ;
}
void afisare ()
{
  FILE *fout ;
  fout = fopen ( "kfib.out" , "wt" ) ;
  fprintf ( fout , "%lld\n" , rez[0][0] ) ;
  fclose ( fout ) ;
}

int main ()
{
    citire () ;

    Z [ 0 ][ 0 ] = 0 ;
    Z [ 0 ][ 1 ] = Z [ 1 ][ 0 ] = Z [ 1 ][ 1 ] = 1 ;
    p = K - 1 ;
    rez [ 0 ][ 0 ] = rez [ 0 ][ 1 ] = rez [ 1 ][ 0 ] = rez [ 1 ][ 1 ] = 1;
    while ( p )
    {

        if ( p & 1 )
            {
                mult ( aux , rez , Z ) ;
                copy ( rez , aux ) ;

            }
        copy ( aux , Z ) ;

        mult ( Z , aux , aux ) ;
        p >>= 1 ;

    }
    afisare () ;

}