#include<fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int mod=666013;

struct Matrice
{
    long long a, b, c, d;
};

Matrice inmultireMatrici(Matrice A, Matrice B)
{
    Matrice C;

    C.a = (A.a * B.a + A.b * B.c) % mod;
    C.b = (A.a * B.b + A.b * B.d) % mod;
    C.c = (A.c * B.a + A.d * B.c) % mod;
    C.d = (A.c * B.b + A.d * B.d) % mod;

    return C;
}

long long putere(Matrice M, long long k)
{
    Matrice R;
    R.a = 1;
    R.b = 0;
    R.c = 0;
    R.d = 1;

    /*if(k==0)
        return 0;
    else if(k==1||k==2)
        return 1;
    else
    {
        while(k!=0)
        {
            if(k%2==1)
            {
                R = inmultireMatrici(R, M);
            }

            M = inmultireMatrici(M, M);
            k/=2;
        }
    }*/

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

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

    return R.d;
}
int main()
{
    long long k;
    Matrice M;
    M.a = 0;
    M.b = 1;
    M.c = 1;
    M.d = 1;

    f>>k;

    long long rezultat = putere(M, k-1);

    g<<rezultat;

    return 0;
}