#include <cstdio>
#include <cstring>

#define MOD 666013
const int DIM = 2;

typedef int Matrice[DIM][DIM];

// Înmulțire matricială: C = A * B (mod MOD)
void inmultire(const Matrice A, const Matrice B, Matrice C) {
    Matrice temporar = {0};
    for (int i = 0; i < DIM; ++i)
        for (int j = 0; j < DIM; ++j)
            for (int k = 0; k < DIM; ++k)
                temporar[i][j] = (temporar[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;

    memcpy(C, temporar, sizeof(temporar));
}

// Ridicare la putere: rezultat = baza ^ putere
void ridica_la_putere(int putere, const Matrice baza, Matrice rezultat) {
    Matrice temp;
    memcpy(temp, baza, sizeof(temp));

    // Inițializare cu matricea identitate
    memset(rezultat, 0, sizeof(Matrice));
    for (int i = 0; i < DIM; ++i)
        rezultat[i][i] = 1;

    while (putere > 0) {
        if (putere & 1) {
            Matrice auxiliar = {0};
            inmultire(rezultat, temp, auxiliar);
            memcpy(rezultat, auxiliar, sizeof(auxiliar));
        }

        Matrice auxiliar = {0};
        inmultire(temp, temp, auxiliar);
        memcpy(temp, auxiliar, sizeof(auxiliar));
        putere >>= 1;
    }
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    int n;
    scanf("%d", &n);

    Matrice baza = {
        {0, 1},
        {1, 1}
    };
    Matrice rezultat;

    if (n == 0) {
        printf("0\n");
    } else {
        ridica_la_putere(n - 1, baza, rezultat);
        printf("%d\n", rezultat[1][1]);
    }

    return 0;
}