#include <stdio.h>

#define MODULO 666013

typedef long long ll;

/* Structura pentru o matrice 2x2 */
typedef struct {
    ll a00, a01, a10, a11;
} Matrice;

/* Inmulteste doua matrice 2x2 modulo MODULO (fara for-uri) */
Matrice inmultire(Matrice A, Matrice B) {
    Matrice rezultat;
    rezultat.a00 = (A.a00 * B.a00 + A.a01 * B.a10) % MODULO;
    rezultat.a01 = (A.a00 * B.a01 + A.a01 * B.a11) % MODULO;
    rezultat.a10 = (A.a10 * B.a00 + A.a11 * B.a10) % MODULO;
    rezultat.a11 = (A.a10 * B.a01 + A.a11 * B.a11) % MODULO;
    return rezultat;
}

/* Ridica matricea M la puterea n folosind exponentierea rapida (O(log n)) */
Matrice ridicare_la_putere(Matrice M, ll n) {
    /* Matricea identitate */
    Matrice identitate = {1, 0, 0, 1};
    while (n > 0) {
        if (n % 2 == 1)
            identitate = inmultire(identitate, M);
        M = inmultire(M, M);
        n /= 2;
    }
    return identitate;
}

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

    ll k;
    fscanf(fisier_intrare, "%lld", &k);

    /* Cazuri de baza: F(0)=0, F(1)=1 */
    if (k == 0) { fprintf(fisier_iesire, "0\n"); return 0; }
    if (k == 1) { fprintf(fisier_iesire, "1\n"); return 0; }

    /*
     * Matricea de tranzitie Z:
     *   | 0  1 |
     *   | 1  1 |
     * Proprietate: Z^(k-1) contine F(k) la pozitia a11
     */
    Matrice tranzitie = {0, 1, 1, 1};
    Matrice putere = ridicare_la_putere(tranzitie, k - 1);

    fprintf(fisier_iesire, "%lld\n", putere.a11 % MODULO);

    fclose(fisier_intrare);
    fclose(fisier_iesire);
    return 0;
}