#include <iostream>
#include <fstream>
#include <stdint.h>

const int64_t MOD = 666013;

void MultMats(int64_t mat1[2][2], const int64_t mat2[2][2]) {
    int64_t res[2][2];
    for(int64_t i = 0; i != 2; ++i) {
        for(int64_t j = 0; j != 2; ++j) {
            res[i][j] = 0;
            for(int64_t k = 0; k != 2; ++k)
                res[i][j] += mat1[i][k] * mat2[k][j];
            res[i][j] %= MOD;
        }
    }
    for(int64_t i = 0; i != 2; ++i) {
        for(int64_t j = 0; j != 2; ++j)
            mat1[i][j] = res[i][j];
    }
}

void Solve(std::istream& fin, std::ostream& fout) {
    int64_t k;
    fin >> k;

    int64_t mat[2][2];
    mat[0][0] = 0; mat[0][1] = 1;
    mat[1][0] = 1; mat[1][1] = 1;

    int64_t res[2][2];
    res[0][0] = 1; res[0][1] = 0;
    res[1][0] = 0; res[1][1] = 1;

    for(; k; k >>= 1) {
        if(k & 1)
            MultMats(res, mat);
        MultMats(mat, mat);
    }

    fout << res[1][0] << '\n';
}

int main() {
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");

    Solve(fin, fout);

    fin.close();
    fout.close();

    return 0;
}