#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
const int R = 666013;
long long N;
int fibo (long long N)
{
    long long i = N - 1, a = 1, b = 0, c = 0, d = 1, t;
    if (N <= 0)
        return 0;
    while (i > 0)
    {
        while (i % 2 == 0)
        {
            t = d * (2 * c + d) % R;
            c = (c * c + d * d) % R;
            d = t;
            i = i / 2;
        }
        t = (d * (b + a) + c * b) % R;
        a = (d * b + c * a) % R;
        b = t;
        i--;
    }
    return a + b;
}

int main()
{
    f >> N;
    g << fibo (N) % R << '\n';

    return 0;
}