#include <cstdio>
#include <cstring>

using namespace std;

const int mod = 666013 ;

int sol[3][3],r[3][3],aux[3][3] ;

inline void mult( int a[3][3] , int b[3][3] , int c[3][3] ){
    for ( int i = 0 ; i < 2 ; i ++ )
        for ( int j = 0 ; j < 2 ; j ++ )
            for ( int k = 0 ; k < 2 ; k ++ )
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j] ) % mod ;
}

inline void exp( int n ){
    while (n>1){
        if (n % 2){
            memset(aux , 0 , sizeof(aux)) ;
            mult(sol , r , aux) ;
            memcpy(r , aux , sizeof(aux)) ;
        }
        memset(aux , 0 , sizeof(aux)) ;
        mult(sol , sol , aux) ;
        memcpy(sol , aux , sizeof(aux)) ;
        n /= 2 ;
    }
    memset(aux , 0 , sizeof(aux)) ;
    mult( sol , r , aux ) ;
    memcpy(sol , aux , sizeof(aux)) ;
}

int main(){
    freopen( "kfib.in" , "r" , stdin ) ;
    freopen( "kfib.out" , "w" , stdout ) ;

    int n ;
    scanf( "%d" , &n ) ;

    sol[1][1] = sol[1][0] = sol[0][1] = 1 ;
    r[0][0] = r[1][1] = 1 ;

    exp(n-1) ;

    printf( "%d\n" , sol[1][1] ) ;

    return 0;
}