#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MOD = 666013;

typedef vector<vector<int> > matrice;

void Resize(matrice &a, int s)
{
    a.resize(s);

    for (int i = 0; i < s; i++)
        a[i].resize(s);
}

matrice inm(matrice a, matrice b)
{
    matrice rez;
    Resize(rez, 2);
    int i, j, k;
    for(i=0; i<a.size(); i++)
    {
        for(j=0; j<a.size(); j++)
        {
            for(k=0; k<a.size(); k++)
            {
                rez[i][j] = (rez[i][j] + 1LL*a[i][k]*b[k][j]) % MOD;
            }
        }
    }
    return rez;
}

matrice epq(matrice m, int p)
{
    matrice aux;

    Resize(aux, 2);

    aux[0][0] = aux[1][1] = 1;

    while(p > 1)
    {
        if(p%2)
        {
            aux = inm(aux, m);
        }
        m = inm(m, m);
        p/=2;
    }
    return inm(m, aux);
}

int main()
{
    int n;
    fin>>n;
    matrice m;

    Resize(m, 2);

    m[0][0] = 0, m[0][1] = m[1][0] = m[1][1] = 1;

    m = epq(m, n-1);

    fout<<m[1][1]%MOD;

    fin.close();
    fout.close();
    return 0;
}