#include <cstdio>
#define REST 666013

int mat[2][2], rez[2][2];

void inmultire( int rez[2][2], int mat[2][2] ) {

    int prod[2][2]; prod[0][0]  = prod[0][1] = prod[1][0] = prod[1][1] = 0;
    for( int i = 0 ; i < 2 ; ++i )
        for( int j = 0 ; j < 2 ; ++j )
            for( int k = 0 ; k < 2 ; ++k ) {
                prod[i][j] +=  ( (long long)rez[i][k] * mat[k][j] ) % REST;
                prod[i][j] %= REST;
            }
    for( int i = 0; i < 2; ++i)
        for( int j = 0; j < 2; ++j)
            rez[i][j] = prod[i][j];
}

void kfib( int k ) {
    int put;
    rez[0][0] = 1; rez[1][0] = 0; rez[0][1] = 0; rez[1][1] = 1;
    mat[0][0] = 0; mat[0][1] = mat[1][0] = mat[1][1] = 1;

    put = 1;
    while( put <= k) {
        if( put & k ) {
            inmultire( rez, mat);
        }
        inmultire(mat, mat);
        put *= 2;
    }
}

int main () {

    FILE *f, *g;
    f = fopen( "kfib.in", "r" );
    g = fopen( "kfib.out", "w" );

    int k;
    fscanf( f, "%d", &k );
    kfib(k);
    fprintf( g, "%d\n", rez[1][0] );

    fclose( f );
    fclose( g );

    return 0;
}