#include    <iostream>
#include    <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

struct matrice
{
    long long a00,a01,a10,a11;
};
matrice A;
void creareA()
{


    A.a00 = 1; A.a01 = 1;

    A.a10 = 1; A.a11 = 0;

}

matrice inmulteste( matrice A, matrice B)
{
    matrice C;

    C.a00 = (A.a00 * B.a00 + A.a01* B.a10) % MOD;
    C.a01 = (A.a00 * B.a01 + A.a01* B.a11) % MOD;
    C.a10 = (A.a10 * B.a00 + A.a11* B.a10) % MOD;
    C.a11 = (A.a10 * B.a01 + A.a11* B.a11) % MOD;

    return C;


}

matrice putere(matrice M, long long k)
{
    matrice I;

    I.a00 = 1; I.a01 = 0;
    I.a10 = 0; I.a11 = 1;

    while(k!=0)
    {
        if(k%2==1)
        {
            I = inmulteste(I, M);
        }

        M = inmulteste(M, M);
        k/=2;
    }

    return I;
}

int main()
{
    long long k;

    f >> k;
    creareA();
        A = putere(A, k-1);

        g << A.a00<< "\n";



    return 0;
}