#include <cstdio>
using namespace std;

const int MOD = 666013;

void mul (int x[2][2], int y[2][2]) {

    int r[2][2];
    r[0][0] = (1LL * x[0][0] * y[0][0] + 1LL * x[0][1] * y[1][0]) % MOD;
    r[0][1] = (1LL * x[0][0] * y[0][1] + 1LL * x[0][1] * y[1][1]) % MOD;
    r[1][0] = (1LL * x[1][0] * y[0][0] + 1LL * x[1][1] * y[1][0]) % MOD;
    r[1][1] = (1LL * x[1][0] * y[0][1] + 1LL * x[1][1] * y[1][1]) % MOD;
    x[0][0] = r[0][0];
    x[0][1] = r[0][1];
    x[1][0] = r[1][0];
    x[1][1] = r[1][1];

}

int main () {

    freopen ("kfib.in", "r", stdin);
    freopen ("kfib.out", "w", stdout);
    int K, M[2][2] = {{0, 1}, {1, 1}}, S[2][2] = {{1, 0}, {0, 1}};
    scanf ("%d", &K);
    K -= 2;
    for (; K; K >>= 1) {
        if (K & 1)
            mul (S, M);
        mul (M, M);
    }
    printf ("%d", S[1][1]);

}