#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 mat[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, mat);
        }
        multiply(mat, mat);
        exp /= 2;
    }

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

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

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

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

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

    fprintf(fout, "%lld\n", mat[1][1]);

    fclose(fin);
    fclose(fout);
    return 0;
}