#include <fstream>

using namespace std;

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

const int MOD = 666013;

int K;

struct Matrix
{
    int N, M;

    int **A;
};

Matrix Special, I2;

static inline void Read ()
{
    f.tie(nullptr);

    f >> K;

    return;
}

static inline int ** Get_Matrix (int N, int M)
{
    int ** ans = new int *[(N + 1)];

    for(int i = 1; i <= N; ++i)
    {
        ans[i] = new int [(M + 1)];

        for(int j = 1; j <= M; ++j)
            ans[i][j] = 0;
    }

    return ans;
}

static inline void Initialize ()
{
    Special.N = Special.M = 2, Special.A = Get_Matrix(2, 2);
    Special.A[1][2] = Special.A[2][1] = Special.A[2][2] = 1;

    I2.N = I2.M = 2, I2.A = Get_Matrix(2, 2);
    I2.A[1][1] = I2.A[2][2] = 1;

    return;
}

static inline void Multiply (Matrix &A, Matrix B)
{
    ///
    Matrix ans;
    ans.N = A.N, ans.M = B.M;
    ans.A = Get_Matrix(ans.N, ans.M);
    ///

    for(int i = 1; i <= A.N; ++i)
        for(int j = 1; j <= B.M; ++j)
        {
            ans.A[i][j] = 0;

            for(int k = 1; k <= A.M; ++k)
                ans.A[i][j] = 1LL * (1LL * ans.A[i][j] + 1LL * A.A[i][k] * B.A[k][j]) % (1LL * MOD);
        }

    A = ans;

    return;
}

static inline Matrix lgput (Matrix n, int p)
{
    Matrix ans = I2, aux = n;

    for(int i = 0; (1 << i) <= p; ++i)
    {
        if(p & (1 << i))
            Multiply(ans, aux);

        Multiply(aux, aux);
    }

    return ans;
}

static inline void Solve ()
{
    Initialize();

    Matrix now = lgput(Special, K - 1);

    Matrix ans;
    ans.N = 1, ans.M = 2, ans.A = Get_Matrix(1, 92);
    ans.A[1][1] = 0, ans.A[1][2] = 1;

    Multiply(ans, now);

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

    return;
}

int main()
{
    Read();

    if(K < 2)
    {
        g << K << '\n';

        return 0;
    }

    Solve();

    return 0;
}