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

#define mod 666013

typedef struct{
    long long m[2][2]; 
}matrice;

matrice inmultire(matrice a, matrice b) {
    matrice c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
            }
        }
    }
    return c;
}

matrice putere(matrice a, int n) {
    matrice id = {{{1, 0}, {0, 1}}};
    while (n > 0) {
        if (n % 2 == 1) {
            id = inmultire(id, a);
        }
        a = inmultire(a, a);
        n /= 2;
    }
    return id;
}   

int main(void)
{
    FILE *fin = NULL;
    FILE *fout = NULL;
    if ((fin = fopen("kfib.in", "r")) == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        return 1;
    }
    if ((fout = fopen("kfib.out", "w")) == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        fclose(fin);
        return 1;
    }

    int k;

    fscanf(fin, "%d", &k);

    fclose(fin);

    matrice Z = {{{1, 1}, {1, 0}}};
    matrice rezultat = putere(Z, k - 1);
    fprintf(fout, "%lld\n", rezultat.m[0][0]);
    fclose(fout);
    return 0;
}