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

#define NR 666013

typedef struct
{

    long long a[2][2];

}Matrice;

Matrice inmultire_matrici(Matrice A, Matrice B)
{
    Matrice C;
    C.a[0][0] = (A.a[0][0]*B.a[0][0] + A.a[0][1]*B.a[1][0]) % NR;
    C.a[0][1] = (A.a[0][0]*B.a[0][1] + A.a[0][1]*B.a[1][1]) % NR;
    C.a[1][0] = (A.a[1][0]*B.a[0][0] + A.a[1][1]*B.a[1][0]) % NR;
    C.a[1][1] = (A.a[1][0]*B.a[0][1] + A.a[1][1]*B.a[1][1]) % NR;
    return C;
}

Matrice lgput(Matrice Z, long long p)
{
    Matrice C = inmultire_matrici(Z, Z);
    if(p == 0)
        return (Matrice){{{1, 0}, {0, 1}}};
    else if(p%2 == 0)
        return lgput(C, p/2);
    else
        return inmultire_matrici(Z, lgput(C, p/2));
}

int main(void)
{
    FILE *in, *out;

    if((in = fopen("kfib.in", "r")) == NULL)
    {
        perror("Eroare la deschiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }

    if((out = fopen("kfib.out", "w")) == NULL)
    {
        perror("Eroare la deschiderea fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    int k;
    if(fscanf(in, "%d", &k) != 1)
    {
        perror("Eroare la citirea datelor din fisierul de intrare");
        exit(EXIT_FAILURE);
    }

    Matrice Z = {{{0, 1}, {1, 1}}};
    Matrice R = lgput(Z, k-1);
    long long fib_k = R.a[1][1]%NR;
    fprintf(out, "%lld\n", fib_k);

    if(fclose(in) != 0)
    {
        perror("Eroare la inchiderea fisierului de intrare");
        exit(EXIT_FAILURE);
    }
    
    if(fclose(out) != 0)
    {
        perror("Eroare la inchiderea fisierului de iesire");
        exit(EXIT_FAILURE);
    }

    return 0;
}