#include <bits/stdc++.h>

#define MAXLOG  31
#define MAXEXP  2
#define EXPN    2

#define MOD     666013

void multiply(int A[MAXEXP][MAXEXP], int B[MAXEXP][MAXEXP], int C[MAXEXP][MAXEXP]) {
    for (int i=0, j, k; i<EXPN; ++i)
        for (j=0; j<EXPN; ++j) {
            C[i][j] = 0;
            for (k=0; k<EXPN; ++k)
                C[i][j] += (1ll*A[i][k]*B[k][j])%MOD;
                C[i][j] %= MOD;
        }
}
int t;
int pow2[MAXLOG][MAXEXP][MAXEXP], ans[2][MAXEXP][MAXEXP];
void fastPow(int base[MAXEXP][MAXEXP], int exp) {
    for (int i=0, j; i<EXPN; ++i)
        for (j=0; j<EXPN; ++j)
            pow2[0][i][j] = base[i][j], ans[0][i][j] = ans[1][i][j] = (i == j);
    for (int i=1; i<MAXLOG; ++i)
        multiply(pow2[i-1], pow2[i-1], pow2[i]);
    int c = 0;
    t = 1;
    for (int i = MAXLOG-1; i>=0; --i) {
        if (c+(1<<i) <= exp)
            c += (1<<i), multiply(pow2[i], ans[t], ans[1-t]), t = 1-t;
    }
}

int N;
int fibBase[2][2] = {{1, 1}, {1, 0}};

#define FILENAME    std::string("kfib")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int32_t main()
{
    input >> N;
    if (N == 0) output << 0 << '\n';
    else if (N == 1) output << 1 << '\n';
    else {
        fastPow(fibBase, N-2);
        output << (ans[t][0][0] + ans[t][1][0])%MOD << '\n';
    }

    return 0;
}