#include <iostream>
#include <fstream>

int initializersFib[2][2]      = {{1, 1}, {1, 0}};
int initializersIdentity[2][2] = {{1, 0}, {0, 1}};

struct Matrix
{
    long long int el[2][2];

    Matrix(int initializers[2][2])
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                el[i][j] = initializers[i][j];
            }
        }
    }

    Matrix()
    {
    }
};

Matrix fib(initializersFib);
Matrix identity(initializersIdentity);

Matrix multiply(Matrix a, Matrix b)
{
    Matrix c;

    c.el[0][0] = ((a.el[0][0] * b.el[0][0]) + (a.el[0][1] * b.el[1][0])) % 666013;
    c.el[0][1] = ((a.el[0][0] * b.el[0][1]) + (a.el[0][1] * b.el[1][1])) % 666013;
    c.el[1][0] = ((a.el[1][0] * b.el[0][0]) + (a.el[1][1] * b.el[1][0])) % 666013;
    c.el[1][1] = ((a.el[1][0] * b.el[0][1]) + (a.el[1][1] * b.el[1][1])) % 666013;

    return c;
}

Matrix power(Matrix a, unsigned p)
{
    if (p == 0)
        return identity;

    if (p == 1)
        return a;

    if (p == 2)
        return multiply(a, a);

    if (p % 2 == 0)
    {
        Matrix c = power(a, p / 2);
        return power(c, 2);
    }
    else
    {
        Matrix c = power(a, p - 1);
        return multiply(c, a);
    }
}

void printMatrix(Matrix a)
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            std::cout << a.el[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main()
{
    std::ifstream in("kfib.in");
    std::ofstream out("kfib.out");

    int term;
    in >> term;

    Matrix c(initializersFib);

    c = power(c, term - 1);

    out << c.el[0][0];

    in.close();
    out.close();

    return 0;
}