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


void generareMatrice(long long m1[][2], long long m2[][2], long long egal[][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                egal[i][j] = (egal[i][j] + m1[i][k] * m2[k][j]) % 666013;
            }
        }
    }
}

void putere(int p, long long transf[][2], long long mat[][2]) {
    long long aux[2][2];
    while (p > 0) {
        if (p % 2 == 1) {
            memset(aux, 0, sizeof(aux));
            generareMatrice(mat, transf, aux);
            memcpy(mat, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        generareMatrice(transf, transf, aux);
        memcpy(transf, aux, sizeof(aux));
        p /= 2;
    }
}

int main() {
    int n;
    long long c[2][2], M[2][2];

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

    fscanf(in, "%d", &n);
    n--;

    c[0][0] = 0;
    c[0][1] = c[1][0] = c[1][1] = 1;

    M[0][0] = M[1][1] = 1;
    M[0][1] = M[1][0] = 0;

    putere(n, c, M);
    fprintf(out, "%lld", M[1][1]);

    fclose(in);
    fclose(out);

    return 0;
}