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

// Definim dimensiunea matricelor ca fiind 2x2
#define DIM 2

// Definim modulo
#define MOD 666013

// Definim matricea Z
int Z[DIM][DIM] = {{0, 1}, {1, 1}};

// Funcție pentru a înmulți două matrici și a returna rezultatul modulo MOD
void multiply_matrices(int A[DIM][DIM], int B[DIM][DIM]) {
    int result[DIM][DIM] = {{0}};
    int i, j, k;
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            for (k = 0; k < DIM; k++) {
                result[i][j] = (result[i][j] + A[i][k] * 1LL * B[k][j]) % MOD;
            }
        }
    }
    // Copiem rezultatul înapoi în matricea A
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            A[i][j] = result[i][j];
        }
    }
}

// Funcție pentru a calcula puterea matricei Z la puterea k modulo MOD
void matrix_power(int result[DIM][DIM], int k) {
    int temp[DIM][DIM];
    int i, j;

    // Inițializăm matricea rezultat ca fiind matricea identitate
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            result[i][j] = (i == j) ? 1 : 0;
        }
    }

    // Ridicăm matricea Z la puterea k folosind algoritmul de exponențiere rapidă pentru matrice
    while (k > 0) {
        if (k % 2 == 1) {
            multiply_matrices(result, Z);
        }
        multiply_matrices(Z, Z);
        k /= 2;
    }
}

int main(void)
{
    FILE *f1=fopen("kfib.in","r"),*f2=fopen("kfib.out","w");
    if(f1==NULL||f2==NULL)
    {
        printf("eroare");
        return 1;
    }

    uint32_t k;
    fscanf(f1,"%d",&k);

    int result[DIM][DIM];
    matrix_power(result, k- 1);
    int FK = result[0][1] % MOD;

    fprintf(f2,"%d",FK);

    fclose(f1);
    fclose(f2);
    return 0;
}