#include <fstream>
#include <vector>

using namespace std;

#define int long long

ifstream in("kfib.in");
ofstream out("kfib.out");
int n;
vector<vector<int>> v;
vector<vector<int>> ans;
int MOD = 666013;

vector<vector<int>> inmulteste(vector<vector<int>> a, vector<vector<int>> b)
{
    vector<vector<int>> ans;
    ans.resize(a.size());

    for(int i = 0; i<ans.size(); i++)
    {
        ans[i].resize(b[0].size());
    }

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

    return ans;
}

vector<vector<int>> lgput(vector<vector<int>> x, int e)
{
    vector<vector<int>> ans;
    ans.push_back({1, 0});
    ans.push_back({0, 1});

    while(e != 0)
    {
        if(e % 2 == 1)
        {
            ans = inmulteste(ans, x);
        }

        x = inmulteste(x, x);
        e /= 2;
    }

    return ans;
}

signed main()
{
    in>>n;

    if(n == 0)
    {
        out<<0;

        return 0;
    }

    v.push_back({0, 1});
    v.push_back({1, 1});

    ans = lgput(v, n - 1);

    vector<vector<int>> rez;

    rez.push_back({1});
    rez.push_back({1});

    rez = inmulteste(ans, rez);

    out<<rez[0][0];

    return 0;
}