#include <bits/stdc++.h>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

long long n,modulo = 666013;
long long m[5][5],sol[5][5];
vector<int>biti;

void lgput()
{
    for (int i = 0; i < biti.size(); i++)
    {
        long long m2[5][5];
        if (biti[i] == 1)
        {
            ///sol = sol * m
            m2[0][0] = sol[0][0];
            m2[0][1] = sol[0][1];
            m2[1][0] = sol[1][0];
            m2[1][1] = sol[1][1];
            sol[0][0] = (m2[0][0] * m[0][0] + m2[0][1] * m[1][0]) % modulo;
            sol[0][1] = (m2[0][0] * m[0][1] + m2[0][1] * m[1][1]) % modulo;
            sol[1][0] = (m2[1][0] * m[0][0] + m2[1][1] * m[1][0]) % modulo;
            sol[1][1] = (m2[1][0] * m[0][1] + m2[1][1] * m[1][1]) % modulo;
        }
        /// m = m * m
        m2[0][0] = m[0][0];
        m2[0][1] = m[0][1];
        m2[1][0] = m[1][0];
        m2[1][1] = m[1][1];
        m[0][0] = (m2[0][0] * m2[0][0] + m2[0][1] * m2[1][0]) % modulo;
        m[0][1] = (m2[0][0] * m2[0][1] + m2[0][1] * m2[1][1]) % modulo;
        m[1][0] = (m2[1][0] * m2[0][0] + m2[1][1] * m2[1][0]) % modulo;
        m[1][1] = (m2[1][0] * m2[0][1] + m2[1][1] * m2[1][1]) % modulo;
    }
}

int main()
{
    in >> n;
    if (n == 0)
        out << 0;
    else if (n == 1 or n == 2)
        out << 1;
    else
    {
        n -= 2;
        while (n != 0)
        {
            biti.push_back(n % 2);
            n /= 2;
        }

        m[0][0] = 0;
        m[0][1] = m[1][0] = m[1][1] = 1;
        sol[0][0] = 0;
        sol[0][1] = sol[1][0] = sol[1][1] = 1;
        lgput();
        out << sol[1][1];
    }
    return 0;
}

/**
sol este z^(n - 1)
m este,la fiecare pas 1 <= i <= log n,matricea z^i
la fiecare pas i,daca al i-lea cel mai insignifiant bit este 1,sol *= m,apoi orice ar fi m *= m
**/