#include <stdio.h>
#include <string.h>

typedef long long ll;

#define MOD 666013

static ll Z[2][2] = {{0, 1}, {1, 1}}, A[2][2];

static void lgput(ll k)
{
    ll C[2][2], AA[2][2];

    if (k <= 1) {
        return;
    }

    memcpy(C, Z, sizeof C);

    lgput(k >> 1);

    A[0][0] = (((Z[0][0] * Z[0][0]) % MOD) + ((Z[0][1] * Z[1][0]) % MOD)) % MOD;
    A[0][1] = (((Z[0][0] * Z[0][1]) % MOD) + ((Z[0][1] * Z[1][1]) % MOD)) % MOD;
    A[1][0] = (((Z[1][0] * Z[0][0]) % MOD) + ((Z[1][1] * Z[1][0]) % MOD)) % MOD;
    A[1][1] = (((Z[1][0] * Z[0][1]) % MOD) + ((Z[1][1] * Z[1][1]) % MOD)) % MOD;

    memcpy(AA, A, sizeof AA);

    if (k & 1) {
        A[0][0] = (((AA[0][0] * C[0][0]) % MOD) + ((AA[0][1] * C[1][0]) % MOD)) % MOD;
        A[0][1] = (((AA[0][0] * C[0][1]) % MOD) + ((AA[0][1] * C[1][1]) % MOD)) % MOD;
        A[1][0] = (((AA[1][0] * C[0][0]) % MOD) + ((AA[1][1] * C[1][0]) % MOD)) % MOD;
        A[1][1] = (((AA[1][0] * C[0][1]) % MOD) + ((AA[1][1] * C[1][1]) % MOD)) % MOD;
    }

    memcpy(Z, A, sizeof Z);
}

int main(void)
{
    ll k;

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

    scanf("%lld", &k);

    lgput(k - 2);

    printf("%lld", (Z[0][1] + Z[1][1]) % MOD);

    return 0;
}