#include <fstream>
using namespace std;

const long long MODULO = 666013;

long long fibo[2] = {1, 1};

long long fibo_copie[2] = {1, 1};

long long mat_rez[4] = {1, 0, 0, 1};

long long mat_a[4] = {0, 1, 1, 1};

long long mat_rez_copie[4];

long long mat_a_copie[4];

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    long long k;
    in >> k;

    if (k == 0)
    {
        out << 0;
        return 0;
    }
    if (k == 1 || k == 2)
    {
        out << 1;
        return 0;
    }

    k -= 2;

    while (k)
    {
        if (k % 2)
        {
            mat_rez_copie[0] = mat_rez[0];
            mat_rez_copie[1] = mat_rez[1];
            mat_rez_copie[2] = mat_rez[2];
            mat_rez_copie[3] = mat_rez[3];

            mat_rez[0] = ((mat_rez_copie[0] * mat_a[0]) % MODULO + (mat_rez_copie[1] * mat_a[2]) % MODULO) % MODULO;
            mat_rez[1] = ((mat_rez_copie[0] * mat_a[1]) % MODULO + (mat_rez_copie[1] * mat_a[3]) % MODULO) % MODULO;
            mat_rez[2] = ((mat_rez_copie[2] * mat_a[0]) % MODULO + (mat_rez_copie[3] * mat_a[2]) % MODULO) % MODULO;
            mat_rez[3] = ((mat_rez_copie[2] * mat_a[1]) % MODULO + (mat_rez_copie[3] * mat_a[3]) % MODULO) % MODULO;
        }

        mat_a_copie[0] = mat_a[0];
        mat_a_copie[1] = mat_a[1];
        mat_a_copie[2] = mat_a[2];
        mat_a_copie[3] = mat_a[3];

        mat_a[0] = ((mat_a_copie[0] * mat_a_copie[0]) % MODULO + (mat_a_copie[1] * mat_a_copie[2]) % MODULO) % MODULO;
        mat_a[1] = ((mat_a_copie[0] * mat_a_copie[1]) % MODULO + (mat_a_copie[1] * mat_a_copie[3]) % MODULO) % MODULO;
        mat_a[2] = ((mat_a_copie[2] * mat_a_copie[0]) % MODULO + (mat_a_copie[3] * mat_a_copie[2]) % MODULO) % MODULO;
        mat_a[3] = ((mat_a_copie[2] * mat_a_copie[1]) % MODULO + (mat_a_copie[3] * mat_a_copie[3]) % MODULO) % MODULO;

        k /= 2;
    }

    fibo_copie[0] = fibo[0];
    fibo_copie[1] = fibo[1];

    fibo[0] = ((fibo_copie[0] * mat_rez[0]) % MODULO + (fibo_copie[1] * mat_rez[2]) % MODULO) % MODULO;
    fibo[1] = ((fibo_copie[0] * mat_rez[1]) % MODULO + (fibo_copie[1] * mat_rez[3]) % MODULO) % MODULO;

    out << fibo[1];

    return 0;
}