#include <stdio.h>

const int MOD = 666013;

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

    A[0][0] = C[0][0];
    A[0][1] = C[0][1];
    A[1][0] = C[1][0];
    A[1][1] = C[1][1];
}

int main() {
    FILE *fin = fopen("kfib.in", "r");
    FILE *fout = fopen("kfib.out", "w");

    if (fin == NULL || fout == NULL) {
        return 0;
    }

    long long K;
    if (fscanf(fin, "%lld", &K) == 1) {
        if (K == 0) {
            fprintf(fout, "0\n");
        } else if (K == 1) {
            fprintf(fout, "1\n");
        } else {
            long long T[2][2] = {{1, 1}, {1, 0}};
            long long REZ[2][2] = {{1, 0}, {0, 1}};
            long long p = K - 1;

            while (p > 0) {
                if (p % 2 == 1) {
                    multiply(REZ, T);
                }
                multiply(T, T);
                p /= 2;
            }

            fprintf(fout, "%lld\n", REZ[0][0]);
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}