#include <cstring>
#include <fstream>

using namespace std;

const int MOD = 666013;
typedef long long i64;

int N;
i64 A[3][3], B[3][3], C[3][3], D[3][3];

void inm1()
{
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            for (int k = 1; k <= 2; ++k)
                C[i][j] += A[i][k] * B[k][j], C[i][j] %= MOD;
}
void inm2()
{
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            for (int k = 1; k <= 2; ++k)
                D[i][j] += B[i][k] * C[k][j], D[i][j] %= MOD;
}
void logPow(int x)
{
    if (x == 1) return;

    for (int i = 1; i <= x; i <<= 1)
    {
        if (i & x)
        {
            memset(C, 0, sizeof(C));
            inm1();
            memcpy(A, C, sizeof(A));
        }

        memset(D, 0, sizeof(D));
        memcpy(C, B, sizeof(C));
        inm2();
        memcpy(B, D, sizeof(B));
    }
}

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

    fin >> N;

    if (N == 0) fout << 0;
    else if (N == 1 || N == 2) fout << 2;
    else
    {
        A[1][1] = 1, A[1][2] = 0, A[2][1] = 0, A[2][2] = 1;
        B[1][1] = 1, B[1][2] = 1, B[2][1] = 1, B[2][2] = 0;
        logPow(N - 2);

        memset(C, 0, sizeof(C));

        B[1][1] = 1, B[1][2] = 1;
        for (int i = 1; i <= 2; ++i)
            for (int k = 1; k <= 2; ++k)
                C[1][i] += B[1][k] * A[k][i], C[1][i] %= MOD;

        fout << C[1][1];
    }

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