#include <fstream>
#define mF "kfib"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
const int M = 666013;
long long a, b = 1, c = 1, d = 1, x = 1, y, z, t = 1, n;
#include <tuple>
#include <functional>
int main()
{
    for (in >> n; n; n >>= 1)
    {
        if (n & 1) std::tie(x, y, z, t) = std::make_tuple(x*a + z*c, x*b + y*d, z*a + t*c, z*b + t*d);
        std::tie(a, b, c, d) = std::make_tuple(a*a + b*b, a*b + b*d, c*a + d*b, c*b + d*d);
        for (auto e: std::initializer_list<std::reference_wrapper<long long>>{a, b, c, d, x, y, z, t}) e %= M;
    }
    out << z;
}