#include <fstream>
#define MOD 666013
#define f in
#define g out

using namespace std;
ifstream in ( "kfib.in" );
ofstream out( "kfib.out" );
int n, a[3][3], aux[3][3], sol[3][3];

void copiaza ( int a[3][3], int b[3][3] ){
    for ( int i = 1; i <= 2; i++ )
        for ( int j = 1; j <= 2; j++ )
            a[i][j] = b[i][j];
}

void inmulteste ( int a[3][3], int b[3][3], int c[3][3] ){
    for ( int i = 1; i <= 2; i++ )
        for ( int j=1; j <= 2; j++ ){
            c[i][j] = 0;
            for ( int k = 1; k <= 2; k++ ){
                c[i][j] += (1LL*a[i][k]*b[k][j])%MOD;
                c[i][j] %= MOD;
            }
        }
}

int main() {
    f>>n;
    if ( n <= 1 )
        g<<n;
    n--;
    a[1][1] = a[1][2] = a[2][1] = 1;
    sol[1][1] = sol[2][2] = 1;
    while (n) {
        if ( n%2 ){
            inmulteste ( a, sol, aux );
            copiaza ( sol, aux );
        }
        inmulteste ( a, a, aux );
        copiaza ( a, aux );
        n /= 2;
    }
    g<<sol[1][1];
    return 0;
}