#include <stdio.h>

#define modulus 666013

void printMat(long long A[2][2]) {

    printf("%lld %lld\n",A[0][0],A[0][1]);
    printf("%lld %lld",A[1][0],A[1][1]);
}

void matMultiply(long long M[2][2],long long N[2][2]) {

    long long AUX[2][2];

    AUX[0][0] = (M[0][0]*N[0][0]+M[0][1]*N[1][0]) % modulus;
    AUX[0][1] = (M[0][0]*N[0][1]+M[0][1]*N[1][1]) % modulus;
    AUX[1][0] = (M[1][0]*N[0][0]+M[1][1]*N[1][0]) % modulus;
    AUX[1][1] = (M[1][0]*N[0][1]+M[1][1]*N[1][1]) % modulus;

    M[0][0] = AUX[0][0];
    M[0][1] = AUX[0][1];
    M[1][1] = AUX[1][1];
    M[1][0] = AUX[1][0];
}

void matExp(long long X[2][2],long long power) {

    long long RES[2][2] = { {0, 1}, {1, 1} };
   // printMat(RES);

    while( power>0 ){

        if( power%2 ) {
           // printMat(RES);
            matMultiply(RES,X);
        }
        matMultiply(X,X);
        power = power/2;
    }

    X[0][0] = RES[0][0];
    X[0][1] = RES[0][1];
    X[1][0] = RES[1][0];
    X[1][1] = RES[1][1];

    printMat(X);
    printf("\n");
}

long long kthFibo(long long k) {

    long long X[2][2] = { {0, 1}, 
                         {1, 1}};
    if( k==0 )
        return 0;

    matExp(X,k-1);

    return X[0][1];
}

int main() {

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

    long long k=0;
    if( fscanf(f,"%lld",&k)!=1 )
        return 0;
    printf(g,"%lld",kthFibo(k));

    fclose(f);
    fclose(g);
    
    return 0;
}