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

#define MOD 666013

void multiplyMatrices(unsigned long long a[2][2], unsigned long long b[2][2], unsigned long long result[2][2]) {
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            result[i][j] = 0;
            for(int k=0;k<2;k++) {
                result[i][j] += (a[i][k] * b[k][j]) % MOD;
            }
        }
    }
}


void logexp(unsigned long long mat[][2], unsigned int power, unsigned long long result[][2]) {
    if(power < 3) {
        if(power == 1) {
            memcpy(result, mat, sizeof(unsigned long long)*4);
        }
        else {
            multiplyMatrices(mat, mat, result);
        }
    }
    else {
        unsigned long long squared[2][2];
        multiplyMatrices(mat, mat, squared);
        if(power % 2 == 0) {
            logexp(squared, power>>1, result);
        }
        else {
            logexp(squared, power>>1, result);
            
            unsigned long long aux[2][2];
            multiplyMatrices(mat, result, aux);
            memcpy(result, aux, sizeof(aux));
        }
    }
}


int main() {
    FILE *input, *output;

    unsigned int k;

    unsigned long long a[2][2] = {{0, 1}, {1, 1}};
    unsigned long long resZ[2][2];

    input = fopen("kfib.in", "r");
    output = fopen("kfib.out", "w");



    fscanf(input, "%d", &k);

    logexp(a, k-1, resZ);

    if(k < 2) {
        fprintf(output, "%d", k);
    }
    else {
        unsigned long long result = resZ[1][1];

        fprintf(output, "%lld", result);

    }

    
    return 0;
}