#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

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

const int MOD = 666013;

inline void mult(long long A[][2], long long B[][2], long long C[][2]) {
    C[0][0] = ((A[0][0] * B[0][0]) %MOD + (A[1][0] * B[0][1] %MOD))%MOD;
    C[0][1] = ((A[0][0] * B[0][1]) %MOD + (A[1][0] * B[1][1] %MOD))%MOD;
    C[1][0] = ((A[0][1] * B[0][0]) %MOD + (A[1][1] * B[0][1] %MOD))%MOD;
    C[1][1] = ((A[0][1] * B[1][0]) %MOD + (A[1][1] * B[1][1] %MOD))%MOD;
}

int lgput(int exp) {
    long long sol[2][2] = { {1, 0}, {0, 1} };
    long long z[2][2] = { {0, 1}, {1, 1} };
    long long aux[2][2];
    for(int i = 0; (1 << i) <= exp; ++i) {
        if( ((1 << i) & exp) ) {
            memcpy(aux, 0, sizeof(aux));
            mult(sol, z, aux);
            memcpy(sol, aux, sizeof(sol));
        }

        memcpy(aux, 0, sizeof(aux));
        mult(z, z, aux);
        memcpy(z, aux, sizeof(aux));
    }
    return sol[1][1];
}

int main() {
    int k;
    fscanf(in, "%d", &k);
    fprintf(out, "%d\n", lgput(k-1));
}