#include <fstream>

using namespace std;

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

const int MOD = 666013;

int K;

int ans[3][3] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 1}};
int aux[3][3] = {{0, 0, 0}, {0, 0, 1}, {0, 1, 1}};

static inline void Add (int &a, int b)
{
    a = (a + b) % MOD;

    return;
}

int main()
{
    f.tie(nullptr);
    f >> K;

    if(K <= 1)
    {
        g << K << '\n';

        return 0;
    }

    for(int i = 0; (1 << i) <= K; ++i)
    {
        if(K & (1 << i))
        {
            int C[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};

            for(int l = 1; l <= 2; ++l)
                for(int c = 1; c <= 2; ++c)
                    for(int k = 1; k <= 2; ++k)
                        Add(C[l][c], (1LL * ans[l][k] * aux[k][c]) % (1LL * MOD));

            for(int l = 1; l <= 2; ++l)
                for(int c = 1; c <= 2; ++c)
                    ans[l][c] = C[l][c];
        }

        int C[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};

        for(int l = 1; l <= 2; ++l)
            for(int c = 1; c <= 2; ++c)
                for(int k = 1; k <= 2; ++k)
                    Add(C[l][c], (1LL * aux[l][k] * aux[k][c]) % (1LL * MOD));

        for(int l = 1; l <= 2; ++l)
            for(int c = 1; c <= 2; ++c)
                aux[l][c] = C[l][c];
    }

    g << ans[2][1] << '\n';

    return 0;
}