#include <stdio.h>

#define MOD 666013

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

int m[2][2] =  {
    { 0, 1 },
    { 1, 1 }
};

void multMat( int a[2][2], int b[2][2], int m, int n, int p ) {
    int l, c, i;

    for ( l = 0; l < m; l++ ) {
        for ( c = 0; c < p; c++ )
            rez[l][c] = 0;
    }
    for ( l = 0; l < m; l++ ) {
        for ( c = 0; c < p; c++ ) {
            for ( i = 0; i < n; i++ )
                rez[l][c] = (rez[l][c] + ((long long)a[l][i] * b[i][c]) % MOD) % MOD;
        }
    }
}

void lgPut( int n ) {
    int l, c;

    if ( n == 1 ) {
        for ( l = 0; l < 2; l++ ) {
            for ( c = 0; c < 2; c++ )
                mat[l][c] = m[l][c];
        }
    } else {
        lgPut( n / 2 );

        multMat( mat, mat, 2, 2, 2 );
        for ( l = 0; l < 2; l++ ) {
            for ( c = 0; c < 2; c++ )
                mat[l][c] = rez[l][c];
        }

        if ( n % 2 == 1 ) {
            multMat( mat, m, 2, 2, 2 );
            for ( l = 0; l < 2; l++ ) {
                for ( c = 0; c < 2; c++ )
                    mat[l][c] = rez[l][c];
            }
        }
    }
}

int main() {
    FILE *fin, *fout;
    int n;

    fin = fopen( "kfib.in", "r" );
    fscanf( fin, "%d", &n );
    fclose( fin );

    lgPut( n + 1 );

    fout = fopen( "kfib.out", "w" );
    fprintf( fout, "%d", mat[0][0] );
    fclose( fout );

    return 0;
}