#include <fstream>
#include <vector>

const int MOD =  666013;

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


void multiplyMatrix(const Matrix &a, Matrix &b)
{
    Matrix res(a.size(), std::vector<int>(b.front().size()));

    for (auto i = 0u; i < a.size(); ++i)
        for (auto j = 0u; j < b.front().size(); ++j)
            for (auto k = 0u; k < b.size(); ++k)
                res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;

    std::swap(res, b);
}

void powLogMatrix(Matrix &z, int p)
{
    Matrix res(z.size(), std::vector<int>(z.size(), 0));
    for (auto i = 0u; i < res.size(); ++i)
        res[i][i] = 1;

    for (auto i = 0; (1 << i) <= p; ++i) {
        if (((1 << i) & p) > 0)
            multiplyMatrix(z, res);

        multiplyMatrix(z, z);
    }

    std::swap(z, res);
}

int getKthFibo(Matrix &z, int K)
{
    powLogMatrix(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 << getKthFibo(z, K);

    return 0;
}