#include <cstdio>

const int MOD = 666013;
int K;

long long REZ[4];
long long A[4] = {1, 1, 1, 0};
long long TZ[4] = {1, 0, 0, 1};

void lgFib (long long b[], int exp, long long acc[]) {
    if (exp == 0) {
        REZ[0] = acc[0];
        REZ[1] = acc[1];
        REZ[2] = acc[2];
        REZ[3] = acc[3];
        return;
    }

    if (exp % 2 == 1) {
        long long aux[4];

        aux[0] = ((b[0] * acc[0]) % MOD + (b[2] * acc[1]) % MOD) % MOD;
        aux[1] = ((b[1] * acc[0]) % MOD + (b[3] * acc[1]) % MOD) % MOD;
        aux[2] = ((b[0] * acc[2]) % MOD + (b[2] * acc[3]) % MOD) % MOD;
        aux[3] = ((b[1] * acc[2]) % MOD + (b[3] * acc[3]) % MOD) % MOD;

        lgFib (b, exp - 1, aux);
    }
    else {
        long long aux[4];

        aux[0] = ((b[0] * b[0]) % MOD + (b[2] * b[1]) % MOD) % MOD;
        aux[1] = ((b[1] * b[0]) % MOD + (b[3] * b[1]) % MOD) % MOD;
        aux[2] = ((b[0] * b[2]) % MOD + (b[2] * b[3]) % MOD) % MOD;
        aux[3] = ((b[1] * b[2]) % MOD + (b[3] * b[3]) % MOD) % MOD;

        lgFib (aux, exp / 2, acc);
    }
}

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

    scanf ("%d", &K);

    lgFib (A, K - 1, TZ);
    printf ("%lld\n", REZ[0]);

    return 0;
}