#include <fstream>
#define  nr 666013
std::ifstream INPUT_FILE("kfib.in");
std::ofstream OUTPUT_FILE("kfib.out");

long long M[2][2],Z[2][2],k;

void init(){
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;

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

void multiply(long long A[2][2], long long B[2][2]){
    long long tmp[2][2];
    tmp[0][0] = 0;
    tmp[1][0] = 0;
    tmp[0][1] = 0;
    tmp[1][1] = 0;
    for (int i = 0; i<2; i++){
        for (int j = 0; j<2; j++){
            for (int k = 0; k<2; k++) tmp[i][j] = (tmp[i][j]+A[i][k]*B[k][j])%nr;
        }
    }

    for (int i = 0; i<2; i++){
        for (int j = 0; j<2; j++) A[i][j] = tmp[i][j];
    }
}

void rowRowFightThePower(long long k) {
    if(k){
        if(k%2){
            multiply(M, Z);
            rowRowFightThePower(k-1);
        }else{
            multiply(Z, Z);
            rowRowFightThePower(k/2);
        }
    }else return;
}

int main()
{
    init();
    INPUT_FILE>> k;
    rowRowFightThePower(k);
    //multiply(M,Z);
    OUTPUT_FILE << M[1][0];
}