#include <stdio.h>
#define PRIM 666013

unsigned long long M[2][2] = {{0, 1}, {1, 1}};

void mat_mult(unsigned long long F[2][2], unsigned long long M[2][2]) {
    unsigned long long x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
    unsigned long long y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
    unsigned long long z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
    unsigned long long w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

    F[0][0] = x%PRIM;
    F[0][1] = y%PRIM;
    F[1][0] = z%PRIM;
    F[1][1] = w%PRIM;
}

void power(unsigned long long F[2][2], unsigned int n) {
    if (n == 0 || n == 1)
        return;


    power(F, n / 2);
    mat_mult(F, F);

    if (n % 2 != 0)
        mat_mult(F, M);
}

unsigned long long fib(unsigned int n) {
    if (n == 0)
        return 0;
    unsigned long long F[2][2] = {{0, 1}, {1, 1}};
    power(F, n);
    return F[0][1];
}

int main() {
    FILE* fis = fopen("kfib.in", "r");
    long long unsigned int k;
    fscanf(fis,"%llu", &k);
    fclose(fis);
    fis = fopen("kfib.out", "r");
    fprintf(fis, "%llu", fib(k));
    fclose(fis);
    return 0;
}