//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

static const int MOD = 666013;

int sol[2][2], m[2][2], aux[2][2],n;

void multiply_1()
{
    memset(aux,0,sizeof(aux));
    for(int i = 0; i < 2; ++i)
    {
        for(int j =0; j < 2; ++j)
        {
            for(int l = 0; l < 2; ++l)
            {
                aux[i][j] = (1LL * aux[i][j] + 1LL * sol[i][l] * m[l][j]) % MOD;
            }
        }
    }
    memcpy(sol, aux, sizeof(sol));
}

void multiply_2()
{
    memset(aux,0,sizeof(aux));
    for(int i =0; i< 2; ++i)
    {
        for(int j =0; j< 2; ++j)
        {
            for(int l = 0; l < 2; ++l)
            {
                aux[i][j] = (1LL * aux[i][j] + 1LL *m[i][l] * m[l][j]) % MOD;
            }
        }
    }
    memcpy(m, aux, sizeof(m));
}

void calc(int p)
{
    int i = 1;
    m[0][0] = 0, m[0][1] = m[1][0] = m[1][1] = 1;

    for( ; i<= p; i<<= 1)
    {
        if(i & p)
        {
            multiply_1();
        }
        multiply_2();
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fin >> n;
    sol[0][0] = sol[1][1] = 1;

    calc(n-1);
    fout << sol[1][1];




    return 0;
}