#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 pll = 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");

    auto matrix_mult = [&](const vector<vector<ll>> &mat1, const vector<vector<ll>> &mat2) -> vector<vector<ll>>
    {
        const int nr_lines1{mat1.size()}, nr_cols1{mat1.front().size()}, nr_cols2{mat2.front().size()};
        vector<vector<ll>> res_mat(nr_lines1, vector<ll>(nr_cols2));
        for (int i = 0; i < nr_lines1; ++i)
        {
            for (int j = 0; j < nr_cols2; ++j)
            {
                for (int k = 0; k < nr_cols1; ++k)
                {
                    res_mat[i][j] = (res_mat[i][j] + mat1[i][k] * mat2[k][j]) % M;
                }
            }
        }
        return res_mat;
    };

    auto fast_exp = [&](vector<vector<ll>> mat, int b) -> vector<vector<ll>>
    {
        const int nr_lines{mat.size()};
        vector<vector<ll>> res_mat(nr_lines, vector<ll>(nr_lines));
        for (int i = 0; i < nr_lines; ++i)
        {
            res_mat[i][i] = 1;
        }
        while (b)
        {
            if (b & 1)
            {
                res_mat = matrix_mult(res_mat, mat);
            }
            mat = matrix_mult(mat, mat);
            b >>= 1;
        }
        return res_mat;
    };

    auto solve = [&](const int n) -> ll
    {
        if (n < 0)
        {
            return 0;
        }
        if (n == 0)
        {
            return 1;
        }
        vector<vector<ll>> rec_mat{{1, 1, 1},
                                   {0, 1, 1},
                                   {0, 1, 0}};
        vector<vector<ll>> res_mat{{1 + 1},
                                   {1},
                                   {1}};
        rec_mat = fast_exp(rec_mat, n - 1);
        return matrix_mult(rec_mat, res_mat)[1].front();
    };

    int T{1};
    // cin >> T;

    while (T--)
    {
        // int left, right;
        // cin >> left >> right;
        int k;
        cin >> k;

        cout << solve(k - 1) % M << "\n";
    }
}