#include <fstream>
#include <iostream>
#include <vector>

#define MOD 666013

using Matrix = std::vector<std::vector<int> >;

void multiply_matrix(Matrix &m1, Matrix &m2)
{
    Matrix res(m1.size(), std::vector<int>(m2.front().size(), 0));

    for (auto i = 0u; i < 2; i++)
        for (auto j = 0u; j < 2; j++)
            for (auto k = 0u; k < 2; k++)
                res[i][j] = (res[i][j] + 1LL * m1[i][k] * m2[k][j]) % MOD;

    std::swap(m2, res);
}

void log_pow_matrix(Matrix &z, int power)
{
    Matrix res(z.size(), std::vector<int>(z.size(), 0));

    for (auto i = 0u; i < z.size(); i++) 
        res[i][i] = 1;

    for (auto i = 0u; (1 << i) <= power; i++) {
        if (power & (1 << i)) 
            multiply_matrix(z, res);

        multiply_matrix(z, z);
    }

    std::swap(res, z);
}

int get_kth_fib(Matrix &z, int k)
{
    log_pow_matrix(z, k - 1);
    return z[1][1];
}

int main()
{
    std::ifstream in("kfib.in");
    std::ofstream out("kfib.out");

    int k;
    in >> k;

    Matrix z{{0, 1}, {1, 1}};

    out << get_kth_fib(z, k) << '\n';

    return 0;
}