#include <fstream>

class Matrix2
{
    unsigned long long x[2][2];

public:
    Matrix2()
    {
        x[0][0] = x[0][1] = x[1][1] = x[1][0] = 0;
    }

    Matrix2 operator+ (const Matrix2& m2)
    {
        Matrix2 eredm;
        int i, j;
        for (i=0; i<2; i++)
        {
            for (j=0; j<2 ;j++)
            {
                eredm.x[i][j] = x[i][j] + m2.x[i][j];
            }
        }
        return eredm;
    }

    Matrix2 operator* (const Matrix2& m2)
    {
        Matrix2 eredm;
        int i, j, k;

        for (i=0; i<2; i++)
        {
            for (j=0; j<2; j++)
            {
                eredm.x[i][j] = 0;
                for (k=0; k<2; k++)
                {
                    eredm.x[i][j] += x[i][k] * m2.x[k][j];
                    eredm.x[i][j] %= 666013;
                }
            }
        }
        return eredm;
    }

    unsigned long long& operator() (int i, int j)
    {
        return x[i][j];
    }
};

template <class T>
T hatv (T alap, unsigned kitevo)
{
    if (kitevo == 1) return alap;

    T fele = hatv (alap, kitevo/2);

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

int main()
{
    Matrix2 m1;

    m1 (0, 0) = 1;
    m1 (0, 1) = 1;
    m1 (1, 0) = 1;
    m1 (1, 1) = 0;

    std::ifstream fin ("kfib.in");
    std::ofstream fout("kfib.out");

    int k;
    fin >> k;
    if (k == 0)
    {
        fout << 0;
        return 0;
    }
    fout << hatv<Matrix2> (m1, k) (1, 0);
}