#include <stdio.h>

#define MOD 666013

void multiply(long long a[2][2], long long b[2][2]) {
    long long c[2][2];
    c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
    c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
    c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
    c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;

    a[0][0] = c[0][0];
    a[0][1] = c[0][1];
    a[1][0] = c[1][0];
    a[1][1] = c[1][1];
}

void power(long long m[2][2], long long exp) {
    long long res[2][2] = {{1, 0}, {0, 1}};
    long long base[2][2] = {{0, 1}, {1, 1}};

    while (exp > 0) {
        if (exp % 2 == 1) {
            multiply(res, m);
        }
        multiply(m, m);
        exp /= 2;
    }

    m[0][0] = res[0][0];
    m[0][1] = res[0][1];
    m[1][0] = res[1][0];
    m[1][1] = res[1][1];
}

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

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

    if (k == 0) {
        fprintf(f2, "0\n");
        fclose(f1);
        fclose(f2);
        return 0;
    }

    long long m[2][2] = {{0, 1}, {1, 1}};
    power(m, k - 1);

    fprintf(f2, "%lld\n", m[1][1]);

    fclose(f1);
    fclose(f2);
    return 0;
}