#include <fstream>
#include <vector>

using namespace std;

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

using matrix = vector<vector<int>>;

static constexpr int MOD = 666013;
static const matrix I_2 = {{1, 0}, {0, 1}}, Fibo_2 = {{0, 1}, {1, 1}};

static const void mat_multiply(matrix &a, matrix b)
{
    matrix c = a;

    for (int i = 0; i < (int)a.size(); ++i)
        for (int j = 0; j < (int)b[0].size(); ++j)
        {
            a[i][j] = 0;

            for (int k = 0; k < (int)a[0].size(); ++k)
            {
                a[i][j] += (1LL * c[i][k] * b[k][j]) % (1LL * MOD);

                if (a[i][j] > MOD)
                    a[i][j] -= MOD;
            }
        }

    return;
}

int main()
{
    int n = 0;

    f.tie(nullptr);
    f >> n;

    if (n <= 1)
    {
        g << n << '\n';
        return 0;
    }

    vector<vector<int>> ans = I_2;
    vector<vector<int>> aux = Fibo_2;

    for (int i = 0; (1 << i) <= (n - 1); ++i)
    {
        if ((n - 1) & (1 << i))
            mat_multiply(ans, aux);

        mat_multiply(aux, aux);
    }

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

    return 0;
}