#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

typedef long long ll;
typedef vector<vector<ll>> matrix;

#define m 666013;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
matrix copy(matrix A)
{
    return {
        {A[0][0], A[0][1]}, {A[1][0], A[1][1]}};
}

matrix mult(matrix A, matrix B)
{
    matrix C(2, vector<ll>(2, 0));
    int i, j, k;
    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j)
            for (k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % m;
    return C;
}

matrix powerMod(matrix M, int P)
{

    matrix Z = {{0, 1}, {1, 1}};

    for (int i = 0; (1 << i) <= P; ++i)
    {
        if (P & (1 << i))
        {

            M = mult(M, Z);
        }

        Z = mult(Z, Z);
    }
    return M;
}

int main()
{

    ll k;
    fin >> k;
    // k = 2707124;
    matrix M = {{1, 0}, {0, 1}};

    M = powerMod(M, k - 1);

    fout << M[1][1];

    return 0;
}