#include <stdio.h>

#define M 666013LL

typedef struct {
    long long a[2][2];
} Matrice;

Matrice inmultire(Matrice x, Matrice y) {
    Matrice r;
    
    r.a[0][0] = (x.a[0][0] * y.a[0][0] + x.a[0][1] * y.a[1][0]) % M;
    r.a[0][1] = (x.a[0][0] * y.a[0][1] + x.a[0][1] * y.a[1][1]) % M;
    r.a[1][0] = (x.a[1][0] * y.a[0][0] + x.a[1][1] * y.a[1][0]) % M;
    r.a[1][1] = (x.a[1][0] * y.a[0][1] + x.a[1][1] * y.a[1][1]) % M;
    
    return r;
}

Matrice putere(Matrice baza, long long exponent) {
    Matrice rezultat = {{{1, 0}, {0, 1}}};

    while (exponent > 0) {
        if (exponent % 2 == 1)
            rezultat = inmultire(rezultat, baza);

        baza = inmultire(baza, baza);
        exponent /= 2;
    }

    return rezultat;
}

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

    if (fin == NULL || fout == NULL) {
        printf("Eroare la deschiderea fisierelor!\n");
        if (fin) fclose(fin);
        if (fout) fclose(fout);
        return 1; 
    }

    long long k;
    if(fscanf(fin, "%lld", &k) != 1){
        printf("Eroare la citirea datelor de intrare!\n");
        fclose(fin);
        fclose(fout);
        return 1;
    }

    if (k == 0) {
        fprintf(fout, "0\n");
    } else if(k == 1){
        fprintf(fout, "1\n");
    } else{
        Matrice z = {{{0, 1}, {1, 1}}};
        Matrice p = putere(z, k);
        fprintf(fout, "%lld\n", p.a[0][1]);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}