#include <fstream>

#define mod 666013

template <typename T>
class Vector
{
protected:
    int nV;
    T *ptrT;
public:
    Vector(void) : nV(0), ptrT(NULL)
    { }
    Vector(int x) : nV(x), ptrT(NULL)
    {
        ptrT = new T[nV];
        for(int i(0); i < nV; i++)
        	ptrT[i] = 0;
    }
    Vector(const Vector<T> &x);
    int size(void)
    {
        return nV;
    }
    void fill(T x)
    {
        for(int i(0); i < nV; i++)
            ptrT[i] = x;
    }
    void push_back(T x);
    void pop_back();
    Vector<T>& operator=(const Vector<T> &x);
    T& operator[](int x)
    {
        if(x < 0 || x >= nV) throw "access violation!";
        return ptrT[x];
    }
    virtual ~Vector(void)
    {
        delete[] ptrT;
        nV = 0;
        ptrT = NULL;
        //std::cout << "vector ";
    }
};

template <typename T>
Vector<T>::Vector(const Vector<T> &x) : nV(x.nV), ptrT(NULL)
{
    ptrT = new T[nV];
    for(int i(0); i < nV; i++)
        ptrT[i] = x.ptrT[i];
}

template <typename T>
void Vector<T>::push_back(T x)
{
    T *aux = new T[nV];
    for(int i(0); i < nV; i++)
        aux[i] = this->ptrT[i];
    delete[] this->ptrT;
    this->ptrT = NULL;
    this->ptrT = new T[nV + 1];
    for(int i(0); i < nV; i++)
        this->ptrT[i] = aux[i];
    this->ptrT[nV] = x;
    this->nV++;
}

template <typename T>
void Vector<T>::pop_back()
{
    T *aux = new T[nV - 1];
}

template <typename T>
Vector<T>& Vector<T>::operator=(const Vector<T> &x)
{
    if(this == &x) return *this;
    nV = x.nV;
    delete[] ptrT;
    ptrT = NULL;
    ptrT = new T[nV];
    for(int i(0); i < nV; i++)
        ptrT[i] = x.ptrT[i];
    return *this;
}

template <typename T>
class Matrice : protected Vector<T>
{
protected:
    int nL, nC;
public:
    Matrice(void) : Vector<T>(), nL(0), nC(0)
    { }
    Matrice(int x, int y) : Vector<T>(x * y), nL(x), nC(y)
    { }
    Matrice(const Matrice<T> &x);
    Matrice<T>& operator=(const Matrice<T> &x);
    T& operator()(int i, int j)
    {
        if(!(i >= 0 && i < nL) || !(j >= 0 && j < nC))
            throw "access violation!";
        return Vector<T>::ptrT[i * nC + j];
    }
    int lines(void)
    {
        return nL;
    }
    int columns(void)
    {
        return nC;
    }
    int storage(void)
    {
        return nL * nC;
    }
    void fill(T x)
    {
        Vector<T>::fill(x);
    }
    void resize(int x, int y);
    Matrice<T> operator*(Matrice<T> x);
    ~Matrice(void)
    {
        nL = nC = 0;
        //std::cout << "matrice ";
    }
};

template <typename T>
Matrice<T>& Matrice<T>::operator=(const Matrice<T> &x)
{
    if(this == &x) return *this;
    this->nL = x.nL;
    this->nC = x.nC;
    this->nV = x.nV;
    delete[] this->ptrT;
    this->ptrT = NULL;
    this->ptrT = new T[this->nV];
    for(int i(0); i < nL * nC; i++)
        this->ptrT[i] = x.ptrT[i];
    return *this;
}

template <typename T>
void Matrice<T>::resize(int x, int y)
{
    this->nL = x;
    this->nC = y;
    this->nV = nL * nC;
    delete[] this->ptrT;
    this->ptrT = NULL;
    this->ptrT = new T[this->nV];
}

template <typename T>
Matrice<T>::Matrice(const Matrice<T> &x) : Vector<T>(x.nV), nL(x.nL), nC(x.nC)
{
    for(int i(0); i < nL * nC; i++)
        this->ptrT[i] = x.ptrT[i];
}

template <typename T>
Matrice<T> Matrice<T>::operator*(Matrice<T> x)
{
    if(nC != x.nL) throw "not permitted!";
    Matrice<T> aux(nL, x.nC);
    for(int i(0); i < nL; i++)
        for(int j(0); j < x.nC; j++)
        {
            aux(i, j) = (1LL * (*this)(i, 0) * x(0, j)) % mod;
            for(int k(1); k < nC; k++)
                aux(i, j) = (aux(i, j) + 1LL * (*this)(i, k) * x(k, j)) % mod;
        }
    return aux;
}

Matrice<int> pow(Matrice<int> x, int p)
{
	if(p == 0) 
	{
		Matrice<int> aux(x.lines(), x.columns());
		for(int i(0); i < x.lines(); i++)
			for(int j(0); j < x.columns(); j++)
				if(i == j) aux(i, j) = 1;
				else aux(i, j) = 0;
	}
	if(p == 1) return x;
	if(p % 2 == 0) return pow(x * x, p / 2);
	return x * pow(x * x, (p - 1) / 2);
}

int main(void)
{
	Matrice<int> a(2, 2), b(1, 2);
	b(0, 0) = 0; b(0, 1) = 1;
	for(int i(0); i < 2; i++)
		for(int j(0); j < 2; j++)
			a(i, j) = 1;
	a(0, 0) = 0;
	std::ofstream out("kfib.out");
	std::ifstream in("kfib.in");
	int nV;
	in >> nV;
	out << (b * pow(a, nV - 1))(0, 1);
	return 0;
}