#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 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;


}

long long putere(matrice A, 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, A);
        }

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

    return I.a00;
}

int main()
{
    long long k, KK;

        f >> k;

        matrice A;

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

        KK = putere(A, k-1);
        g << KK;




    return 0;
}