#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];
}

long long fib(long long n) {
    if (n == 0) return 0;
    
    long long res[2][2] = {{1, 0}, {0, 1}};
    long long base[2][2] = {{1, 1}, {1, 0}};
    
    n = n - 1;
    while (n > 0) {
        if (n & 1) multiply(res, base);
        multiply(base, base);
        n >>= 1;
    }
    
    return res[0][0];
}

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

    if (fscanf(fin, "%lld", &k) == 1) {
        fprintf(fout, "%lld\n", fib(k));
    }

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