#include    <stdio.h>
#include    <cstring>

#define MOD 666013

int K;
long long baseCase[2][2] = { {0, 1},
                             {1, 1} };

long long Result[2][2] = { {0, 1},
                           {0, 0} };

void Multiply(long long A[2][2], long long B[2][2]) {
    long long C[2][2];

    memset(C, 0, sizeof(C));

    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            for (int k = 0; k <= 1; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;

    memcpy(A, C, sizeof(C));
}

long long logPower(int K) {
    while (K) {
        if (K & 1)
            Multiply(Result, baseCase);

        K >>= 1;
        Multiply(baseCase, baseCase);
    }

    return Result[0][0];
}

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

    scanf("%d", &K);
    printf("%d", logPower(K));
}