#include <fstream>

using namespace std;

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

const int MOD = 666013;

int K;

int ans[3][3], aux[3][3];

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;
    }

    ans[1][1] = ans[2][2] = 1;
    aux[1][1] = 0, aux[1][2] = aux[2][1] = aux[2][2] = 1;

    for(int i = 0; (1 << i) <= K; ++i)
    {
        if(K & (1 << i))
        {
            int A[3][3];
            for(int l = 1; l <= 2; ++l)
                for(int c = 1; c <= 2; ++c)
                    A[l][c] = 0;
            for(int l = 1; l <= 2; ++l)
                for(int c = 1; c <= 2; ++c)
                    for(int k = 1; k <= 2; ++k)
                        Add(A[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] = A[l][c];
        }

        int A[3][3];
        for(int l = 1; l <= 2; ++l)
            for(int c = 1; c <= 2; ++c)
                A[l][c] = 0;
        for(int l = 1; l <= 2; ++l)
            for(int c = 1; c <= 2; ++c)
                for(int k = 1; k <= 2; ++k)
                    Add(A[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] = A[l][c];
    }

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

    return 0;
}