#include <stdio.h>

#define MOD 666013

typedef struct {
    long a, b, c, d;
} Matrice;

long inmultire_modulara(long a, long b) 
{
    long rez = 0;
    a %= MOD;
    while (b > 0) {
        if (b & 1) {
            rez = (rez + a) % MOD;
        }
        a = (a + a) % MOD;
        b >>= 1;
    }
    return rez;
}

Matrice inmultire(Matrice x, Matrice y)
{
    Matrice r;
    r.a = (inmultire_modulara(x.a, y.a) + inmultire_modulara(x.b, y.c)) % MOD;
    r.b = (inmultire_modulara(x.a, y.b) + inmultire_modulara(x.b, y.d)) % MOD;
    r.c = (inmultire_modulara(x.c, y.a) + inmultire_modulara(x.d, y.c)) % MOD;
    r.d = (inmultire_modulara(x.c, y.b) + inmultire_modulara(x.d, y.d)) % MOD;

    return r;
}

Matrice ridicare(Matrice baza, long exp)
{
    Matrice rezultat;
    rezultat.a = 1;
    rezultat.b = 0;
    rezultat.c = 0;
    rezultat.d = 1;

    while(exp > 0)
    {
        if(exp & 1)
        {
            rezultat = inmultire(rezultat, baza);
        }

        baza = inmultire(baza, baza);
        exp >>= 1;
    }

    return rezultat;
}

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

    if (fin == NULL || fout == NULL) 
    { 
        printf("eroare deschidere fisier\n");
        return 0;
    }

    long k = 0;
    long val_citita;

    while (fscanf(fin, "%ld", &val_citita) == 1) {
        k = val_citita;
    }

    if(k == 0)
    {
        fprintf(fout, "0\n");
        fclose(fin);
        fclose(fout);
        return 0;
    }

    Matrice baza;
    baza.a = 1; baza.b = 1;
    baza.c = 1; baza.d = 0;

    Matrice rezultat = ridicare(baza, k - 1);

    fprintf(fout, "%ld\n", rezultat.a);

    fclose(fin);
    fclose(fout);

    return 0;
}