#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

long long N, Sol[3][3];

static inline void LgPut (int p)
{
    Sol[1][1] = 1;
    Sol[1][2] = 0;
    Sol[2][1] = 0;
    Sol[2][2] = 1;

    long long Aux[3][3];

    Aux[1][1] = 0;
    Aux[1][2] = 1;
    Aux[2][1] = 1;
    Aux[2][2] = 1;

    for(int i = 0; (1 << i) <= p; ++i)
    {
        if(p & (1 << i))
        {
            long long A = 0, B = 0, C = 0, D = 0;

            A = Sol[1][1] * Aux[1][1] + Sol[1][2] * Aux[2][1];
            B = Sol[1][1] * Aux[1][2] + Sol[1][2] * Aux[2][2];

            C = Sol[2][1] * Aux[1][1] + Sol[2][2] * Aux[2][1];
            D = Sol[2][1] * Aux[1][2] + Sol[2][2] * Aux[2][2];

            A %= MOD;
            B %= MOD;
            C %= MOD;
            D %= MOD;

            Sol[1][1] = A;
            Sol[1][2] = B;
            Sol[2][1] = C;
            Sol[2][2] = D;
        }

        long long A = 0, B = 0, C = 0, D = 0;

        A = Aux[1][1] * Aux[1][1] + Aux[1][2] * Aux[2][1];
        B = Aux[1][1] * Aux[1][2] + Aux[1][2] * Aux[2][2];

        C = Aux[2][1] * Aux[1][1] + Aux[2][2] * Aux[2][1];
        D = Aux[2][1] * Aux[1][2] + Aux[2][2] * Aux[2][2];

        A %= MOD;
        B %= MOD;
        C %= MOD;
        D %= MOD;

        Aux[1][1] = A;
        Aux[1][2] = B;
        Aux[2][1] = C;
        Aux[2][2] = D;
    }

    return;
}

int main()
{
    f.tie(NULL);

    f >> N;
    --N;

    if(N == 0 || N == 1)
    {
        g << 1 << '\n';

        return 0;
    }

    LgPut(N - 1);

    long long ans = Sol[1][2] + Sol[2][2];

    ans %= MOD;

    g << ans << '\n';

    return 0;
}