#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
const int MOD=666013;
struct matrice2x2
{
    long long v11, v12, v21, v22;
};
matrice2x2 fact, initial, rez, rezfinal;
matrice2x2 inmultire (matrice2x2 x, matrice2x2 y)
{
    matrice2x2 z;
    z.v11=((x.v11*y.v11)%MOD+(x.v12*y.v21)%MOD)%MOD;
    z.v12=((x.v11*y.v12)%MOD+(x.v12*y.v22)%MOD)%MOD;
    z.v21=((x.v21*y.v11)%MOD+(x.v22*y.v21)%MOD)%MOD;
    z.v22=((x.v21*y.v12)%MOD+(x.v22*y.v22)%MOD)%MOD;
    return z;
}
void ridicare_la_putere_in_timp_logaritmic (int p)
{
    while(p)
    {
        if(p%2==0)
        {
            fact=inmultire(fact, fact);
            p/=2;
        } else
        {
            rez=inmultire(fact, rez);
            p--;
        }
    }
}
int main()
{
    int n;
    fact.v11=1; fact.v12=1; fact.v21=1;
    initial.v11=1; initial.v12=1;
    rez.v11=1; rez.v12=0; rez.v21=0; rez.v22=1;
    fin>>n;
    ridicare_la_putere_in_timp_logaritmic(n-1);
    fout<<rez.v11;
    return 0;
}