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

#define MOD 666013

typedef struct {
    uint64_t a, b, c, d;
} matrice;

matrice mul(matrice m1, matrice m2) {
    matrice r;
    r.a = (m1.a * m2.a + m1.b * m2.c) % MOD;
    r.b = (m1.a * m2.b + m1.b * m2.d) % MOD;
    r.c = (m1.c * m2.a + m1.d * m2.c) % MOD;
    r.d = (m1.c * m2.b + m1.d * m2.d) % MOD;
    return r;
}

// ridicare matrice la putere cu exponentiere binara
matrice exp(matrice base, uint64_t exp) {
    matrice rez = {1, 0, 0, 1}; // matrice identitate
    while (exp) {
        if (exp & 1) {
            rez = mul(rez, base);
        }
        base = mul(base, base);
        exp >>= 1;
    }
    return rez;
}

// calculeaza fib(k) folosind ridicarea matricii de tranzitie
uint64_t fibo(uint64_t k) {
    if (k == 0) return 0;
    matrice m = {0, 1, 1, 1};   // matrice tranzitie fibonaci
    matrice p = exp(m, k - 1);
    return p.d;                 
}

int main() {
    uint64_t k;
    FILE *input = fopen("kfib.in", "r");
    FILE *output = fopen("kfib.out", "w");

    if (!input || !output) {
        fprintf(stderr, "Eroare deschidere fisiere!");
        exit(-1);
    }

    if (fscanf(input, "%lu", &k) != 1) {
        fprintf(stderr, "Eroare la citire k!\n");
        exit(-1);
    }

    uint64_t rez = fibo(k);
    fprintf(output, "%lu", rez);

    fclose(input);
    fclose(output);
    return 0;
}