#include <cstdio>

using namespace std;

int v[3][3] =
{
    0, 0, 0,
    0, 0, 1,
    0, 1, 1,
};

int cv[3][3] =
{
    0, 0, 0,
    0, 0, 1,
    0, 1, 1,
};

inline void inmult (int a[3][3], int b[3][3])
{
    int rez[3][3];
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            rez[i][j] = 0;

    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            for (int h = 1; h <= 2; ++h)
            {
                long long x = 1LL * a[i][h] * b[h][j];
                x %= 666013LL;

                rez[i][j] += (int)x;
                rez[i][j] %= 666013;
            }

    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            a[i][j] = rez[i][j];
}

inline void put (int k)
{
    if (k < 2) return;
    put (k / 2);

    inmult (v, v);
    if (k & 1) inmult (v, cv);
}

int main ()
{
    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);

    int k;
    scanf ("%d", &k);

    if (!k)
    {
        printf ("0\n");
        return 0;
    }

    put (k - 1);
    printf ("%d\n", v[2][2]);

    return 0;
}