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

#define MOD 666013

void mult(long long a[2][2], long long b[2][2]) {
    long long tmp[2][2] = {{0, 0}, {0, 0}};
    int i, j, k;

    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j)
            for (k = 0; k < 2; ++k)
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;

    memcpy(a, tmp, sizeof(tmp));
}

void mat_pow(long long exp, long long res[2][2], const long long base[2][2]) {
    res[0][0] = 1; res[0][1] = 0;
    res[1][0] = 0; res[1][1] = 1;

    long long curr[2][2];
    memcpy(curr, base, sizeof(curr));

    while (exp) {
        if (exp % 2) {
            mult(res, curr);
            exp--;
        } else {
            mult(curr, curr);
            exp /= 2;
        }
    }
}

int main() {
    FILE *in = fopen("kfib.in", "r");
    FILE *out = fopen("kfib.out", "w");

    long long k;
    fscanf(in, "%lld", &k);

    if (k == 0) {
        fprintf(out, "0\n");
    } else {
        long long base[2][2] = {{1, 1}, {1, 0}};
        long long ans[2][2];
        mat_pow(k - 1, ans, base);
        fprintf(out, "%lld\n", ans[0][0]);
    }

    fclose(in);
    fclose(out);
    return 0;
}