#include <stdio.h>
#define modP 666013

typedef long long lli;

typedef struct {
    lli a, b;
    lli c, d;
} mat;

mat matprod( mat M, mat N ) {
    mat retval;
    retval.a = ( M.a * N.a + M.b * N.c ) % modP;
    retval.b = ( M.a * N.b + M.b * N.d ) % modP;
    retval.c = ( M.c * N.a + M.d * N.b ) % modP;
    retval.d = ( M.c * N.b + M.d * N.d ) % modP;
    return retval;
}

mat pwr( mat M, int P ) {
    if( P == 0 ) {
        mat retval;
        retval.a = retval.d = 1;
        retval.b = retval.c = 0;
        return retval;
    } else {
        mat val = pwr( M, P / 2 );
        val = matprod( val, val );
        if( P & 1 ) {
            val = matprod( val, M );
            val.a %= modP;
            val.b %= modP;
            val.c %= modP;
            val.d %= modP;
        }
        return val;
    }
}

int main( ) {
    FILE * fin, * fout;
    fin = fopen( "kfib.in", "r" );
    fout = fopen( "kfib.out", "w" );

    int K;
    fscanf( fin, "%d", &K );

    mat M;
    M.a = M.b = M.c = 1;
    M.d = 0;

    fprintf( fout, "%lld\n", pwr( M, K ).b );

    fclose( fin );
    fclose( fout );
}