#include <fstream>
#include <vector>

std::ifstream be("kfib.in");
std::ofstream ki("kfib.out");

class matrix
{
    public:
    unsigned long long elem[2][2];
    matrix operator= (const matrix& m2)
    {
        this->elem[0][0] = m2.elem[0][0];
        this->elem[0][1] = m2.elem[0][1];
        this->elem[1][0] = m2.elem[1][0];
        this->elem[1][1] = m2.elem[1][1];
        return *this;
    }
};

matrix alap;

matrix szoroz (const matrix& m1, const matrix& m2)
{
    matrix eredm;
    eredm.elem[0][0] = (m1.elem[0][0]*m2.elem[0][0] + m1.elem[0][1]*m2.elem[1][0]) % 666013;
    eredm.elem[0][1] = (m1.elem[0][0]*m2.elem[0][1] + m1.elem[0][1]*m2.elem[1][1]) % 666013;
    eredm.elem[1][0] = (m1.elem[1][0]*m2.elem[0][0] + m1.elem[1][1]*m2.elem[1][0]) % 666013;
    eredm.elem[1][1] = (m1.elem[1][0]*m2.elem[0][1] + m1.elem[1][1]*m2.elem[1][1]) % 666013;
    return eredm;
}

matrix hatv (int kitevo)
{
    if (kitevo == 1) return alap;

    matrix fele = hatv (kitevo/2);

    if (kitevo%2) return szoroz ( szoroz(fele, fele), alap);
    else return szoroz (fele, fele);
}

void kiir(const matrix& m)
{
    ki << m.elem[0][0] << " " << m.elem[0][1] << "\n" << m.elem[1][0] << " " << m.elem[1][1] << "\n\n";
}

int main()
{
    int n;
    be >> n;

    alap.elem[0][0] = 0;
    alap.elem[0][1] = 1;
    alap.elem[1][0] = 1;
    alap.elem[1][1] = 1;

    matrix eredmeny = hatv (n-1);

    ki << eredmeny.elem[1][1];
}