#include <fstream>

#define MOD 666013

void multiply(int A[][2], int B[][2], int C[][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) {
            C[i][j] = 0;
            for (int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
        }
}

int getKthFibo(int K, int M[][2])
{
    int A[2][2] = { {1, 0}, {0, 1} }, AUX[2][2];

    for (int i = 0; (1 << i) <= K; ++i) {
        if (K & (1 << i)) {
            multiply(M, A, AUX);

            A[0][0] = AUX[0][0];
            A[0][1] = AUX[0][1];
            A[1][0] = AUX[1][0];
            A[1][1] = AUX[1][1];
        }


        multiply(M, M, AUX);
        M[0][0] = AUX[0][0];
        M[0][1] = AUX[0][1];
        M[1][0] = AUX[1][0];
        M[1][1] = AUX[1][1];
    }

    return A[1][1];
}

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

    int K;
    in >> K;
    in.close();

    int M[2][2] = { {0, 1}, {1, 1} };
    out << getKthFibo(K - 1, M);
    out.close();

    return 0;
}