#include <fstream>

using namespace std;

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

const int MOD = 666013 ;

int Z[2][2], M[2][2] ;
int N ;

inline void mult ( int A[2][2], int B[2][2] ) {
    int C[2][2] ;
    for ( int i = 0; i < 2; ++i ) {
        for ( int j = 0; j < 2; ++j ) {
            C[i][j] = 0 ;
            for ( int k = 0; k < 2; ++k ) {
                C[i][j] += 1LL * A[i][k] * B[k][j] % MOD ;
                if ( C[i][j] >= MOD ) C[i][j] -= MOD ;
            }
        }
    }

    for ( int i = 0; i < 2; ++i ) {
        for ( int j = 0; j < 2; ++j ) {
            A[i][j] = C[i][j] ;
        }
    }
}

inline void powr ( int P, int M[2][2] ) {
    M[0][0] = M[1][1] = 1 ;

    for ( ; P ; P >>= 1 ) {
        if ( P & 1 ) {
            mult ( M, Z ) ;
        }

        mult ( Z, Z ) ;
    }
}

int main ( void ) {
    //fscanf ( fopen ( FIN, "r" ) , "%d", &N ) ;
	f>>N;

    Z[0][0] = 0, Z[0][1] = 1 ;
    Z[1][0] = 1, Z[1][1] = 1 ;

    powr ( N - 1, M ) ;

    //fprintf ( fopen ( FOU, "w" ) , "%d", M[1][1] ) ;
	g<<M[1][1];
}