#include <fstream.h>

int K, P = 666013, p, i;
long long A, M[2][2][32];

void read() {

    ifstream fin("kfib.in");
    fin >> K;
    fin.close();

}

void setMatrix(int k, long long a, long long b, long long c, long long d) {

    M[0][0][k] = a, M[0][1][k] = b, M[1][0][k] = c, M[1][1][k] = d;

}

void mulMatrix(int k, int i) {
    
    long long X[2][2] = {{M[0][0][k], M[0][1][k]}, {M[1][0][k], M[1][1][k]}};

    setMatrix(
            p + 1,
            (X[0][0] * M[0][0][i] + X[0][1] * M[1][0][i]) % P,
            (X[0][0] * M[0][1][i] + X[0][1] * M[1][1][i]) % P,
            (X[1][0] * M[0][0][i] + X[1][1] * M[1][0][i]) % P,
            (X[1][0] * M[0][1][i] + X[1][1] * M[1][1][i]) % P
            );

}

void solve() {

    if (K == 0) { A = 0; return; }
    if (K <= 2) { A = 1; return; }

    K-= 2;

    M[0][0][0] = 0, M[0][1][0] = M[1][0][0] = M[1][1][0] = 1;

    for (p = 1; (1 << p) <= K; ++p) {

        M[0][0][p] = (M[0][0][p - 1] * M[0][0][p - 1] + M[0][1][p - 1] * M[1][0][p - 1]) % P;
        M[0][1][p] = (M[0][0][p - 1] * M[0][1][p - 1] + M[0][1][p - 1] * M[1][1][p - 1]) % P;
        M[1][0][p] = (M[1][0][p - 1] * M[0][0][p - 1] + M[1][1][p - 1] * M[1][0][p - 1]) % P;
        M[1][1][p] = (M[1][0][p - 1] * M[0][1][p - 1] + M[1][1][p - 1] * M[1][1][p - 1]) % P;

    }

    M[1][0][p + 1] = 0, M[0][0][p + 1] = M[0][1][p + 1] = M[1][1][p + 1] = 1;

    for (i = 0; i <= p; ++i) {

        if ((1 << i) & K) {

            int X[2][2] = {{M[0][0][p + 1], M[0][1][p + 1]}, {M[1][0][p + 1], M[1][1][p + 1]}};

            M[0][0][p + 1] = (X[0][0] * M[0][0][i] + X[0][1] * M[1][0][i]) % P;
            M[0][1][p + 1] = (X[0][0] * M[0][1][i] + X[0][1] * M[1][1][i]) % P;
            M[1][0][p + 1] = (X[1][0] * M[0][0][i] + X[1][1] * M[1][0][i]) % P;
            M[1][1][p + 1] = (X[1][0] * M[0][1][i] + X[1][1] * M[1][1][i]) % P;

        }

    }

    A = M[0][1][p + 1];

}

void write() {

    ofstream fout("kfib.out");
    fout << A << '\n';
    fout.close();

}

int main() {

    read();
    solve();
    write();
    return 0;

}