#include <stdio.h>

const int MOD = 666013;

struct Matrix
{
    long long a[2][2];
};

struct Matrix multiply(struct Matrix x, struct Matrix y)
{
    struct Matrix r;

    r.a[0][0] =
        (x.a[0][0] * y.a[0][0] +
         x.a[0][1] * y.a[1][0]) % MOD;

    r.a[0][1] =
        (x.a[0][0] * y.a[0][1] +
         x.a[0][1] * y.a[1][1]) % MOD;

    r.a[1][0] =
        (x.a[1][0] * y.a[0][0] +
         x.a[1][1] * y.a[1][0]) % MOD;

    r.a[1][1] =
        (x.a[1][0] * y.a[0][1] +
         x.a[1][1] * y.a[1][1]) % MOD;

    return r;
}

int main()
{
    FILE *in, *out;
    long long K;

    in = fopen("kfib.in", "r");
    out = fopen("kfib.out", "w");

    fscanf(in, "%lld", &K);

    if (K == 0)
    {
        fprintf(out, "0\n");
        return 0;
    }

    struct Matrix sol =
    {{
        {1, 0},
        {0, 1}
    }};

    struct Matrix a =
    {{
        {0, 1},
        {1, 1}
    }};

    K--;

    while (K)
    {
        if (K % 2)
            sol = multiply(sol, a);

        a = multiply(a, a);
        K /= 2;
    }

    fprintf(out, "%lld\n", sol.a[1][1]);

    fclose(in);
    fclose(out);

    return 0;
}