#include <stdio.h>

#define MOD 666013 // Modulul din problema ca sa nu l screim d prea multe ori

// Facem functia care inmulteste doua matrici de 2X2

void inmultire_matrice(long long A[2][2], long long B[2][2]) {
    long long C[2][2]; // Matrice temporara ca sa nu suprascriem datele din A din greseala

    // Facem %Mod ca sa nu avem overflow
    C[0][0] = (A[0][0] * B[0][0] % MOD + A[0][1] * B[1][0] % MOD) % MOD;
    C[0][1] = (A[0][0] * B[0][1] % MOD + A[0][1] * B[1][1] % MOD) % MOD;
    C[1][0] = (A[1][0] * B[0][0] % MOD + A[1][1] * B[1][0] % MOD) % MOD;
    C[1][1] = (A[1][0] * B[0][1] % MOD + A[1][1] * B[1][1] % MOD) % MOD;

    // punem rezultatul in A
    A[0][0] = C[0][0]; A[0][1] = C[0][1];
    A[1][0] = C[1][0]; A[1][1] = C[1][1];
}

// Facem programul de la ridicare la putere logaritmica dar il adaptam pt matrici
void exp_log_matrice(long long Z[2][2], long long n) {
    
    long long id[2][2] = {
        {1, 0},
        {0, 1}
    };

    while (n > 0) {
        if (n % 2 == 1) {               // Daca bitul e 1
            inmultire_matrice(id, Z);  // p = p * x % MOD (dar cu matrici)
        }
        inmultire_matrice(Z, Z);        // x = x * x % MOD (patratul bazei)
        n = n / 2;                      // Taiem bitul analizat
    }

    // Punem raspunsul final inapoi in Z pentru a-l trimite in main
    Z[0][0] = id[0][0]; Z[0][1] = id[0][1];
    Z[1][0] = id[1][0]; Z[1][1] = id[1][1];
}

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

    if (fin == NULL) {
        printf("Eroare la deschiderea fisierului\n");
        return 0;
    }

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

    if (K == 0) { //cazul pt k = 0
        fprintf(fout, "0\n");
    } else {
        long long Z[2][2] = {
            {0, 1},
            {1, 1}
        };

        // pt al k-lea termen fibonacci ne trb Z la puterea k - 1
        exp_log_matrice(Z, K - 1);

        fprintf(fout, "%lld\n", Z[1][1]); //solutia se afla pe coloana 1 linia 1 pt ca acolo se afla al k lea termen, al k-1 termen fibo se afla pe Z[0][1]
    }

    fclose(fin);
    fclose(fout);

    return 0;
}