#include <stdio.h>
#include <stdlib.h>

#define MOD 666013
void copia(long long dest[2][2], long long src[2][2]) {
    for (int lin = 0; lin < 2; lin++)
        for (int col = 0; col < 2; col++)
            dest[lin][col] = src[lin][col];
}

void mat_mult(long long x[2][2], long long y[2][2], long long res[2][2]) {
    res[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD;
    res[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD;
    res[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD;
    res[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD;
}

void mat_pow(long long base[2][2], int exp) {
    long long id[2][2] = { {1, 0}, {0, 1} };
    long long temp[2][2];

    while (exp > 0) {
        if (exp % 2 == 1) {
            mat_mult(id, base, temp);
            copia(id, temp);
        }
        mat_mult(base, base, temp);
        copia(base, temp);
        exp /= 2;
    }
    copia(base, id);
}

long long fib_k(int k) {
    if (k == 0)
        return 0;
    long long mat[2][2] = { {1, 1}, {1, 0} };
    mat_pow(mat, k);
    return mat[0][1];
}

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

    if (fin == NULL)
    {
        perror("eroare la deschiderea fisierului de intrare");
        exit(-1);
    }
    if (fout == NULL)
    {
        perror("erooare la deschiderea fisierului de iesire");
        exit(-1);
    }
    int k;
    fscanf(fin, "%d", &k);
    long long rezultat = fib_k(k);
    fprintf(fout, "%lld\n", rezultat);
    fclose(fin);
    fclose(fout);
    return 0;
}