#include <stdio.h>

void produsmat2x2(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]) % 666013;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % 666013;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % 666013;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % 666013;
    
    for(int i = 0; i < 2; i ++)
        for(int j = 0; j < 2; j ++)
            A[i][j] = C[i][j];
}

long long exp_log(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    
    long long I[2][2] = {{1,0},{0,1}};
    long long Z[2][2] = {{0,1},{1,1}};
    n--;
    while(n > 0) {
        if(n % 2 == 1) {
            produsmat2x2(I,Z);
        }
        produsmat2x2(Z,Z);
        n = n/2;
    }
    return I[1][1];
}

int main() {
    FILE *fin = NULL;
    fin = fopen("kfib.in", "r");
    if(fin == NULL)
        return -1;
    int n;
    fscanf(fin,"%d", &n);
    
    FILE *fout = NULL;
    fout = fopen("kfib.out", "w");
    fprintf(fout, "%lld", exp_log(n));
    
    fclose(fin);
    fclose(fout);
    return 0;
}

//0 | 1 1 2 3 5 8 13 21 34