#include <fstream>

void copy(int a[][2], int b[][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = b[i][j];
        }
    }
}

void multiply(int a[][2], int b[][2]) {
    int c[][2] = { 0, 0, 0, 0};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % 666013;
            }
        }
    }
    copy(a, c);
}

int main(int argc, const char * argv[]) {
    int k, c[][2] = { 1, 1, 0, 0 }, z[][2] = { 1, 1, 1, 0 };
    std::ifstream f("kfib.in");
    f >> k;
    k -= 2;
    while(k) {
        if (k % 2 == 0) {
            multiply(z, z);
            k /= 2;
        } else {
            multiply(c, z);
            k--;
        }
    }
    std::ofstream g("kfib.out");
    g << c[0][0] << '\n';
    return 0;
}