#include <stdio.h>
#define MODULO 666013;

//algortim pentru inmultirea matricilor
void MatrixProduct(long long int A[2][2], long long int B[2][2], long long int resultArray[2][2]) {
    long long int tempArray[2][2];

    for(int i = 0; i < 2; ++i) {
        //inmultirea se face linie coloana, mai apoi mod MODULO
        for(int j = 0; j < 2; ++j) {
            tempArray[i][j] = 0;
            for(int k = 0; k < 2; ++k) {
                tempArray[i][j] += (A[i][k] * B[k][j]) % MODULO;
                tempArray[i][j] %= MODULO;
            }
        }
    }

    for (int i = 0; i < 2; i++) {
        //retinem rezultatul in resultArray
        for (int j = 0; j < 2; j++) {
            resultArray[i][j] = tempArray[i][j];
        }
    }
}

//ridicarea la putere a unei matrici, cu un exponent dat
void matrixPower(long long int A[2][2], long long int exponent) {
    long long int resultArray[2][2] = {{1, 0}, {0, 1}};
    long long int baseArray[2][2];

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

    //cam cea mai rapida metoda la care m-am gandit pentru ridicarea la putere a unei matrici
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            MatrixProduct(resultArray, baseArray, resultArray);
        }

        MatrixProduct(baseArray, baseArray, baseArray);
        exponent /= 2;
    }

    for (int i = 0; i < 2; i++) {
        //retinem rezultatul in A
        for (int j = 0; j < 2; j++) {
            A[i][j] = resultArray[i][j];
        }
    }
}

long long int getFibonacciModulo(long long int kTh) {

    long long int kThFibonacciElement[2][2] = {{1, 1}, {1, 0}};
    matrixPower(kThFibonacciElement, kTh - 1);

    return kThFibonacciElement[0][0];
}

int main() {
    long long int kTh;
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%lld", &kTh);

    long long int result = getFibonacciModulo(kTh);

    printf("%lld\n", result);

    return 0;
}