#include <iostream>
#include <fstream>

#define PRIME 666013
typedef unsigned long long int u64;
u64 matrix[2][2] = {0, 1, 1, 1};

void multiply(u64 matrixA[2][2], u64 matrixB[2][2]) {
    u64 res[2][2] = {0};

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            u64 element = 0;
            for (int k = 0; k < 2; ++k) {
                element = (element % PRIME + (matrixA[i][k] % PRIME * matrixB[k][j] % PRIME) % PRIME) % PRIME;
            }
            res[i][j] = element;
        }
    }

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            matrixA[i][j] = res[i][j];
        }
    }
}

u64 ans[2][2] = {1, 0, 0, 1};

void pow(int exp) {
    while (exp > 0) {
        if (exp & 1) {
            multiply(ans, matrix);
        }

        exp >>= 1;
        multiply(matrix, matrix);
    }
}

int main() {
    std::ifstream input("kfib.in");
    std::ofstream output("kfib.out");
    int k;
    input >> k;

    if (k == 0) {
        output << 0;
        return 0;
    }

    pow(k - 1);

    output << ans[1][1];

    return 0;
}