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

#define MOD 666013

void printMatrix(long long a[][2]) {
    printf("\n");
    for (long long i = 0; i < 2; i++) {
        for (long long j = 0; j < 2; j++) {
            printf("%lld ", a[i][j]);
        }
        printf("\n");
    }
}

void inmultire(long long a[][2], long long b[][2], long long c[][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;
}

long long fibo(int p) {
    long long a[2][2] = {{0, 1}, {1, 1}}, rez[2][2] = {{1, 0}, {0, 1}};
    long long temp[2][2];

    while(p) {
        if(p % 2 == 1) {
            inmultire(rez, a, temp);
            memcpy(rez, temp, sizeof(temp));
        }

        inmultire(a, a, temp);
        memcpy(a, temp, sizeof(temp));
        //printMatrix(a);

        p /= 2;
    }

    return rez[1][1];
}

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

    int k;

    fscanf(input, "%d", &k);
    fprintf(output, "%lld\n", fibo(k - 1));
    
    fclose(input);
    fclose(output);

    return 0;
}