#include <iostream>
#include <fstream>

using namespace std;

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

const int P = 666013;

int putere(int n)
{
    long long a = 0, b = 1, c = 1;
    long long p1 = 1, p3 = 1, p2 = 0;
    long long x, y, z;
    while(n > 0)
        if(n % 2 == 0)
        {
            x = a * a + b * b;
            y = a * b + b * c;
            z = b * b + c * c;
            a = x % P;
            b = y % P;
            c = z % P;
            n /= 2;
        }
        else
        {
            x = a * p1 + b * p2;
            y = b * p1 + c * p2;
            z = c * p3 + b * p2;
            p1 = x % P;
            p2 = y % P;
            p3 = z % P;
            n--;
        }
    return p3;
}

int main()
{
    int K;
    f >> K;
    g << putere(K - 1);
    f.close();
    g.close();
    return 0;
}