# include <iostream>
# include <fstream>

# include <string.h>

# define MOD 666013

using namespace std;

long long fib[2][2] = { {1, 1}, {1, 0} };
long long unu[2][2] = { {1, 0}, {0, 1} };

void copym( long long a[2][2], long long b[2][2] ) {
    int i, j;
    for ( i = 0; i < 2; i ++ )
        for ( j = 0; j < 2; j ++ )
            b[i][j] = a[i][j];
}

void clear( long long mat[2][2] ) {
    int i, j;
    for ( i = 0; i < 2; i ++ )
        for ( j = 0; j < 2; j ++ )
            mat[i][j] = 0;
}

void mod( long long mat[2][2] ) {
    int i, j;
    for ( i = 0; i < 2; i ++ )
        for ( j = 0; j < 2; j ++ )
            mat[i][j] %= MOD;
}

void prod( long long a[2][2], long long b[2][2], long long c[2][2] ) {
    clear( c );
    int i, j, k;

    for ( i = 0; i < 2; i ++ )
        for ( j = 0; j < 2; j ++ )
            for ( k = 0; k < 2; k ++ )
                c[i][k] += a[i][j] * b[j][k];

    mod( c );
}

void power( long long a[2][2], long long p, long long r[2][2] ) {
    if ( p == 0 )
        copym( unu, r );
    else {
        long long aux[2][2], aux2[2][2];
        power( a, p / 2, aux );
        if ( p % 2 == 0 ) {
            prod( aux, aux, r );
        } else {
            prod( aux, aux, aux2 );
            prod( aux2, a, r );
        }
    }
}

int main() {
    ifstream fin( "kfib.in" );
    ofstream fout( "kfib.out" );

    int n;
    long long r[2][2];

    fin >> n;

    power( fib, n, r );

    fout << r[0][1] << endl;

    fin.close();
    fout.close();

    return 0;
}