#include <stdio.h>

#define MODULO 666013;

void matrixMultiply(long long int A[2][2], long long int B[2][2], long long int result[2][2]) {
    long long int temp[2][2];
    int i, j, k;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            temp[i][j] = 0;
            for (k = 0; k < 2; k++) {
                temp[i][j] += (A[i][k] * B[k][j]) % MODULO;
                temp[i][j] %= MODULO;
            }
        }
    }

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            result[i][j] = temp[i][j];
        }
    }
}

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];
    int i, j, k;

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

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            matrixMultiply(resultArray, baseArray, resultArray);
        }

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

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

long long int getFibonacciModulo(long long int k) {
    if (k <= 1)
        return k;

    long long int kThFibonacciElement[2][2] = {{1, 1}, {1, 0}};
    matrixPower(kThFibonacciElement, k - 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;
}