#include <fstream>

using namespace std;

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

long long int k, matrice[3][3], solutie[3][3], sol[3][3];
int mod = 666013, cnt;
bool cond;

void ProdusMatrice(long long m1[3][3], long long m2[3][3])
{
    long long m3[3][3];
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1 ; j <= 2; j++)
        {
            m3[i][j] = 0;
            for(int k = 1; k <= 2; k++)
            {
                m3[i][j] += m1[i][k] * m2[k][j] % mod;
                m3[i][j] %= mod;
            }
        }
    }
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            m1[i][j] = m3[i][j];
}

int main()
{
    fin >> k;
    k--;
    matrice[2][1] = matrice[1][2] = matrice[2][2] = 1;
    while(k != 0)
    {
        if(k % 2 == 1)
        {
            if(!cond)
            {
                cond = true;
                solutie[1][1] = matrice[1][1];
                solutie[1][2] = matrice[1][2];
                solutie[2][1] = matrice[2][1];
                solutie[2][2] = matrice[2][2];
            }
            else
                ProdusMatrice(solutie, matrice);
        }
        ProdusMatrice(matrice, matrice);
        k /= 2;
    }
    sol[1][2] = 1;
    ProdusMatrice(sol, solutie);
    fout << sol[1][2];
}