#include <stdio.h>

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

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

void fib_k(int k) {
    int i;
    long a, b, c, d;
    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)) {
            a = M[0][0];
            b = M[0][1];
            c = M[1][0];
            d = M[1][1];

            M[0][0] = (a * Z[0][0] * 1LL + b * Z[1][0]) % 666013;
            M[0][1] = (a * Z[0][1] * 1LL + b * Z[1][1]) % 666013;
            M[1][0] = (c * Z[0][0] * 1LL + d * Z[1][0]) % 666013;
            M[1][1] = (c * Z[0][1] * 1LL + d * Z[1][1]) % 666013;
        }

        a = Z[0][0];
        b = Z[0][1];
        c = Z[1][0];
        d = Z[1][1];

        Z[0][0] = (a * a * 1LL + b * c) % 666013;
        Z[0][1] = (a * b * 1LL + b * d) % 666013;
        Z[1][0] = (c * a * 1LL + d * c) % 666013;
        Z[1][1] = (c * b * 1LL + d * d) % 666013;
    }
}

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;
}