#include <stdio.h>
#include <stdlib.h>
#define MOD 666013 // modulul cerut în problemă

// copiază matricea src în dest
void copia(long long dest[2][2], long long src[2][2])
{
    for (int lin = 0; lin < 2; lin++)
        for (int col = 0; col < 2; col++)
            dest[lin][col] = src[lin][col];
}
void mat_mult(long long x[2][2], long long y[2][2], long long res[2][2])
{
    res[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD;
    res[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD;
    res[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD;
    res[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD;
}

// ridică matricea base la puterea exp folosind exponentiere rapidă
void mat_pow(long long base[2][2], int exp)
{
    long long id[2][2] = { {1, 0}, {0, 1} }; // matricea identitate
    long long temp[2][2]; // pentru calcule intermediare
    while (exp > 0)
    {
        if (exp % 2 == 1) 
        {
            mat_mult(id, base, temp); 
            copia(id, temp);
        }
        mat_mult(base, base, temp); 
        copia(base, temp);
        exp /= 2;
    }
    copia(base, id); 
}
// calculează al k-lea termen Fibonacci folosind matrice
long long fib_k(int k)
{
    if (k == 0)
        return 0;
    long long mat[2][2] = { {1, 1}, {1, 0} };
    mat_pow(mat, k);
    return mat[0][1]; // F(k) este pe poziția [0][1]
}

int main()
{
    FILE* fin = fopen("kfib.in", "r");
    FILE* fout = fopen("kfib.out", "w");
    if (fin == NULL)
    {
        perror("eroare la deschiderea fisierului de intrare");
        exit(-1);
    }
    if (fout == NULL)
    {
        perror("erooare la deschiderea fisierului de iesire");
        exit(-1);
    }
    int k;
    fscanf(fin, "%d", &k); 
    long long rezultat = fib_k(k); // calculăm F(k)
    fprintf(fout, "%lld\n", rezultat); 
    fclose(fin);
    fclose(fout);
    return 0;
}