#include <cstdio>

#define M 666013

using namespace std;

int k;
long long r[2][2] = {0, 1, 1, 1};

void mult(long long x[2][2], long long y[2][2])
{
    long long s[2][2];

    s[0][0] = ((x[0][0] * y[0][0]) % M + (x[0][1] * y[1][0]) % M) % M;
    s[0][1] = ((x[0][0] * y[0][1]) % M + (x[0][1] * y[1][1]) % M) % M;
    s[1][0] = ((x[1][0] * y[0][0]) % M + (x[1][1] * y[1][0]) % M) % M;
    s[1][1] = ((x[1][0] * y[0][1]) % M + (x[1][1] * y[1][1]) % M) % M;

    r[0][0] = s[0][0];
    r[0][1] = s[0][1];
    r[1][0] = s[1][0];
    r[1][1] = s[1][1];
}

void p(int k)
{
    long long aux[2][2];

    if(k < 2)
        return;

    if(k % 2 == 0)
    {
        mult(r, r);
        p(k / 2);
        return;
    }

    for(int i = 0; i < 2; ++ i)
        for(int j = 0; j < 2; aux[i][j] = r[i][j ++]);

    mult(r, r);
    p(k / 2);
    mult(r, aux);
}

int main()
{
    freopen("kfib.in", "r", stdin);
    scanf("%d\n", &k);

    p(k);

    freopen("kfib.out", "w", stdout);

    if(k == 0)
        printf("0\n");
    else
        printf("%lld\n", r[0][1]);

    return 0;
}