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

typedef unsigned long long ull;

ull fibo(ull n)
{
    ull mat[][2] = {{0, 1}, {1, 1}}, cmat[][2] = {{0, 1}, {1, 1}};
    for(ull i = 1; i < n; ++i)
    {
        ull a = mat[0][0], b = mat[0][1], c = mat[1][0], d = mat[1][1];
        mat[0][0] = (a * cmat[0][0] % m + b * cmat[1][0] % m) % m;
        mat[0][1] = (a * cmat[0][1] % m + b * cmat[1][1] % m) % m;
        mat[1][0] = (c * cmat[0][0] % m + d * cmat[1][0] % m) % m;
        mat[1][1] = (c * cmat[0][1] % m + d * cmat[1][1] % m) % m;
    }
    return mat[1][1];
}

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);
    if(!n)
    {
        fprintf(pf, "0");
        exit(0);
    }
    fprintf(pf, "%llu", fibo(n - 1));
    fclose(pf);
    return 0;
}