#include <stdio.h>
#include <stdlib.h>
#define m 666013

typedef unsigned long long ull;

ull* f;

ull fibo(ull n)
{
    #define ternary(a, b, c) ((a) ? (b) : (c))
    return ternary(f[n], f[n], ternary(n <= 1, n, f[n] = (fibo(n - 1) % m + fibo(n - 2) % m) % m));
}

int main(void)
{
    FILE* pf;
    do{
        pf = fopen("kfib.in", "r");
    }while(pf == NULL);
    ull n;
    fscanf(pf, "%llu", &n);
    fclose(pf);
    do{
        pf = fopen("kfib.out", "w");
    }while(pf == NULL);
    do{
        f = (ull*)calloc(1e8, sizeof(ull));
    }while(f == NULL);
    fprintf(pf, "%llu", fibo(n));
    fclose(pf);
    return 0;
}