/*
    |Fn-0| = |1, 1| * |Fn-1|
    |Fn-1| = |1, 0| * |Fn-2|
*/

#include <cstdio>

const int MOD = 666013;
using namespace std;

int N;
int    Answer[2][2] = { {1, 0}, {0, 1} };
int  Constant[2][2] = { {1, 1}, {1, 0} };
int Auxiliary[2][2] = { {0, 0}, {0, 0} };

inline void mul( int A[2][2], int B[2][2], int C[2][2] ) {

    for( int i = 0; i <= 1; i ++ ) {
    for( int j = 0; j <= 1; j ++ ) {
        C[i][j] = 0;

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

    return;
}

inline void cop( int A[2][2], int B[2][2] ) {

    for( int i = 0; i <= 1; i ++ )
    for( int j = 0; j <= 1; j ++ )
        A[i][j] = B[i][j];

    return;
}

int main () {

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

    scanf( "%d", &N ); N --;

    if( N <= 1 )
        printf( "%d\n", N );
    else {

        while( N ) {

            if( N % 2 ) {
                mul( Answer, Constant, Auxiliary );
                cop( Answer, Auxiliary );
            }

            mul( Constant, Constant, Auxiliary );
            cop( Constant, Auxiliary );

            N /= 2;
        }
    }

    printf( "%d\n", Answer[0][0] );

    return 0;
}