#include <fstream>
#define MOD 666013
#define LL long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
LL k,V[2][2],Rez[2][2];

inline void Multiply(LL x[2][2], LL y[2][2])
{
    LL aux00, aux01, aux10, aux11;
    aux00 = (x[0][0]*y[0][0] + x[0][1]*y[1][0]) % MOD;
    aux01 = (x[0][0]*y[0][1] + x[0][1]*y[1][1]) % MOD;
    aux10 = (x[1][0]*y[0][0] + x[1][1]*y[1][0]) % MOD;
    aux11 = (x[1][0]*y[0][1] + x[1][1]*y[1][1]) % MOD;
    x[0][0] = aux00;
    x[0][1] = aux01;
    x[1][0] = aux10;
    x[1][1] = aux11;
}

inline void Putere(int n)
{
    V[0][1] = V[1][0] = V[1][1] = Rez[0][0] = Rez[1][1] = 1;
    for(; n; n>>=1)
    {
        if(n & 1) Multiply(Rez, V);
        Multiply(V, V);
    }
}

int main()
{
    fin >> k;
    if(!--k) fout << "0\n";
    else
    {
        Putere(k);
        fout << Rez[1][1] << '\n';
    }
    fout.close();
    return 0;
}