#include <fstream>


using namespace std;

int read_k()
{
    int k;
    ifstream fin("kfib.in");
    fin >> k;
    fin.close();
    return k;
}

// O(n): 20 points solution
int calc_fib(int k)
{
    if (k == 0)
    {
        return 0;
    }
    int nr1 = 0;
    int nr2 = 1;
    int nr_aux;
    while(k > 1) {
        nr_aux = (nr1 + nr2) % 666013;
        nr1 = nr2;
        nr2 = nr_aux;
        k --;
    }
    return nr2;
}

// O(log2n)
long long calc_fib_log(int k)
{
    if (k <= 1)
    {
        return k;
    }
    k -= 1;
    long long a0 = 0, a1 = 1, a2 = 1, a3 = 1;
    long long t0, t1, t2, t3;
    long long f0 = 1, f1 = 0, f2 = 0, f3 = 1;

    while(k > 0) {
        if (k % 2 == 1) {
            t0 = ((f0 * a0) + (f1 * a2)) % 666013;
            t1 = ((f0 * a1) + (f1 * a3)) % 666013;
            t2 = ((f0 * a2) + (f2 * a3)) % 666013;
            t3 = ((f2 * a1) + (f3 * a3)) % 666013;

            f0 = t0; f1 = t2; f2 = t2; f3 = t3;
        }

        t0 = ((a0 * a0) + (a1 * a2)) % 666013;
        t1 = ((a0 * a1) + (a1 * a3)) % 666013;
        t2 = ((a0 * a2) + (a2 * a3)) % 666013;
        t3 = ((a2 * a1) + (a3 * a3)) % 666013;

        a0 = t0; a1 = t1; a2 = t2; a3 = t3;

        k /= 2;
    }
    return f3;
}

void print_result(int result)
{
    ofstream fout("kfib.out");
    fout << result;
    fout.close();
}

int main()
{
    int k = read_k();
    // int result = calc_fib(k);
    int result = calc_fib_log(k);
    print_result(result);
    return 0;
}