#include <stdio.h>
// Să se calculeze al K-lea termen al şirului modulo 666013.

#define MOD 666013

typedef struct
{
    long long a[2][2];
} Matrice;

Matrice multiply(Matrice x, Matrice y)
{
    Matrice r = {0};

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                r.a[i][j] = (r.a[i][j] +
                             x.a[i][k] * y.a[k][j]) %
                            MOD;

    return r;
}

Matrice power(Matrice base, long long exp)
{
    Matrice result = {{{1, 0}, {0, 1}}}; // matrice identitate

    while (exp)
    {
        if (exp & 1)
            result = multiply(result, base);

        base = multiply(base, base);
        exp >>= 1;
    }

    return result;
}

int main()
{

    // int Z[2][2] = {{0, 1}, {1, 1}};
    //  Mi = M1 * Z^(i-1)  M1 = (0 1 ; 1 1)

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

    long long K;
    fscanf(fin, "%lld", &K);

    if (K == 0)
    {
        fprintf(fout, "0");
        return 0;
    }
    if (K == 1)
    {
        fprintf(fout, "1");
        return 0;
    }

    Matrice Z = {{{0, 1}, {1, 1}}};
    Matrice P = power(Z, K - 1);

    fprintf(fout, "%lld", P.a[1][1]);

    fclose(fin);
    fclose(fout);

    return 0;
}