#include <stdio.h>
#include <string.h>

long Z[2][2] = {
    {0, 1},
    {1, 1}
};

long M[2][2] = {
    {1, 0},
    {0, 1}
};

long TMP[2][2];

void prod_matrix(long A[2][2], long B[2][2], long C[2][2]) {
    int i, j, k;
    for (i = 0; i < 2; i++) {
        for (j = 0 ; j < 2; j++) {
            C[i][j] = 0;
            for (k = 0; k < 2; k++) {
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % 666013;
            }
        }
    }
}

void fib_k(int k) {
    int i;
    M[0][0] = 1;
    M[0][1] = 0;
    M[1][0] = 0;
    M[1][1] = 1;

    for (i = 0 ; (1 << i) <= k; i++) {
        if (k & (1 << i)) {
            prod_matrix(Z, M, TMP);
            memcpy(M, TMP, sizeof(TMP));
        }

        prod_matrix(Z, Z, TMP);
        memcpy(Z, TMP, sizeof(TMP));
    }
}

int main(int argc, char **argv) {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    long k;

    scanf("%d\n", &k);

    fib_k(k -1);

    printf("%d\n", M[1][1]);

	return 0;
}