#include <stdio.h>

#define MOD 666013

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

// Funcție pentru a înmulți două matrici și a returna rezultatul modulo MOD
void multiply_matrices(int result[2], int M[2], int K) {
    int temp[2][2] = {{0}};
    temp[0][0] = M[0];
    temp[1][0] = M[1];

    int i, j;
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            result[i] = (result[i] + temp[i][j] * 1LL * Z[j][K]) % MOD;
        }
    }
}

// Funcție pentru a calcula puterea matricei Z la puterea k modulo MOD
void matrix_power(int result[2], int k) {
    int i;
    result[0] = 0;
    result[1] = 1;

    int M[2] = {0, 1}; // Matricea M(1)

    // 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, M, 0);
        }
        multiply_matrices(M, M, 1);
        k /= 2;
    }
}

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

    if(f1==NULL||f2==NULL)
    {
        printf("eroare");
        return 1;
    }
    int K;
    fscanf(f1,"%d",&K);

    int FK;
    // Calculăm al K-lea termen al șirului Fibonacci modulo MOD
    int result[2];
    matrix_power(result, K - 1);
    FK = result[1]; // Elementul din colțul din dreapta-sus al matricei rezultate

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

    fclose(f1);
    fclose(f2);

    return 0;
}