#include "bits/stdc++.h"
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
const int M = 666013;


int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");

    int K;
    cin >> K;

    auto mod = [](const ll a) -> ll
    {
        return a % M;
    };

    auto matrix_mult = [&mod](const vector<vector<ll>> &mat1, const vector<vector<ll>> &mat2) -> vector<vector<ll>>
    {
        const int res_nr_lines = mat1.size(), res_nr_cols = mat2.front().size(), nr_cols_mat1 = mat1.front().size();
        vector<vector<ll>> res(res_nr_lines, vector<ll>(res_nr_cols));
        for (int i = 0; i < res_nr_lines; ++i)
        {
            for (int j = 0; j < res_nr_cols; ++j)
            {
                for (int k = 0; k < nr_cols_mat1; ++k)
                {
                    res[i][j] = mod(res[i][j] + mat1[i][k] * mat2[k][j]);
                }
            }
        }
        return res;
    };

    auto fast_matrix_exp = [&matrix_mult](vector<vector<ll>> base, int exp) -> vector<vector<ll>>
    {
        vector<vector<ll>> res(base.size(), vector<ll>(base.front().size()));
        res[0][0] = res[1][1] = 1;
        while (exp)
        {
            if (exp & 1)
            {
                res = matrix_mult(res, base);
            }
            base = matrix_mult(base, base);
            exp /= 2;
        }
        return res;
    };

    vector<vector<ll>> const_mat(2, vector<ll>(2, 1)), res_mat(1, vector<ll>(2, 1));
    const_mat[0][0] = res_mat[0][0] = 0;

    cout << matrix_mult(res_mat, fast_matrix_exp(const_mat, K - 1))[0][1];
}