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

int Z[2][2], fibo[2][2];

void inmultire(int a[][2], int b[][2], int c[][2]) {
    int rest = 666013;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            for(int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % rest;
            } 
        }
    }
}

void fast_exp(int p, int M[][2]) {
    int c[2][2], aux[2][2];

    memcpy(c, Z, sizeof(Z));
    M[0][0] = M[1][1] = 1; // matricea identitate

    for(int i = 0; (1 << i) <= p; i++) {
        if((p & (1 << i))) {
            memset(aux, 0, sizeof(aux));
            inmultire(M, c, aux);
            memcpy(M, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        inmultire(c, c, aux);
        memcpy(c, aux, sizeof(aux));
    }
}

int main() {
    int K;

    FILE *in = fopen("kfib.in", "r");
    FILE *out = fopen("kfib.out", "w");

    fscanf(in, "%d", &K);
    fclose(in);

    Z[0][0] = 0;
    Z[0][1] = Z[1][0] = Z[1][1] = 1;

    fast_exp(K - 1, fibo); 

    fprintf(out, "%d", fibo[1][1]);
    fclose(out);

    return 0;
}