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

#define MODULO 666013

/*
    Avem indicatia (Fn-2 Fn-1) * (0,1 ; 1 1) = (Fn-1 Fn)
    => scoatem ultimul element in functie de astea
    => Mi = M1 * Z^(i-1)
    avem nevoie de o functie care sa inmulteasca doua matrici
    implementam matricea sub forma de structura ca sa lucram mai usor
*/

typedef struct{
    uint64_t m[2][2];
}MATRICE;

MATRICE inmultire_matrici(MATRICE A, MATRICE B)
{
    MATRICE RES;

    RES.m[0][0] = (1LL * A.m[0][0] * B.m[0][0] + 1LL * A.m[0][1] * B.m[1][0]) % MODULO; // evitam overflow
    RES.m[0][1] = (1LL * A.m[0][0] * B.m[0][1] + 1LL * A.m[0][1] * B.m[1][1]) % MODULO;
    
    RES.m[1][0] = (1LL * A.m[1][0] * B.m[0][0] + 1LL * A.m[1][1] * B.m[1][0]) % MODULO;
    RES.m[1][1] = (1LL * A.m[1][0] * B.m[0][1] + 1LL * A.m[1][1] * B.m[1][1]) % MODULO;
    //am adaugat 1LL ca altfel dadea overflow;

    return RES;
}

MATRICE return_matrice_identitate(){
    MATRICE I;

    I.m[0][0] = 1;
    I.m[0][1] = 0;
    
    I.m[1][0] = 0;
    I.m[1][1] = 1;

    return I;
}

//facem functia de ridicare la putere rapida a unei matrici (M^pow)
//este analoaga exponentierii rapide de la problema de dinainnte
MATRICE exponentiere_rapida_matrice(MATRICE M, uint64_t pow)
{
    MATRICE res = return_matrice_identitate();
    while (pow > 0){
        if (pow % 2 == 1){
            res = inmultire_matrici(res, M);
        }
        M = inmultire_matrici(M, M);
        pow/=2;
    }

    return res;
}

uint64_t k_fibo(uint64_t k)
{
    if (k == 0){
        return 0; 
    }
    if (k == 1){
        return 1;
    }

    MATRICE Z_i;
    Z_i.m[0][0] = 0;
    Z_i.m[0][1] = 1;
    Z_i.m[1][0] = 1;
    Z_i.m[1][1] = 1;

    MATRICE RES = exponentiere_rapida_matrice(Z_i, k - 1);

    return ((RES.m[0][1]) % MODULO);
}

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

    uint64_t k;
    fscanf(fin, "%lu", &k);
    
    uint64_t res = k_fibo(k);
    fprintf(fout, "%lu", res);

    fclose(fin);
    fclose(fout);
    return 0;
}