#include <iostream>
#include <fstream>

using namespace std;

typedef unsigned long long ull;
#define MOD 666013LL

class Matrice
{
    public:
        Matrice();
        Matrice(int nl, int nc);
        Matrice(const Matrice &m);

        virtual ~Matrice();
        ull getValue(int l, int c);
        void setValue(int l, int c, ull value);
        bool isSquare();
        void print();
        void modul(ull v);

        Matrice operator=(Matrice m);
        Matrice toPower(int power);

        friend Matrice operator+(Matrice m1, Matrice m2);
        friend Matrice operator-(Matrice m1, Matrice m2);
        friend Matrice operator*(Matrice m1, Matrice m2);

        int nr_linii;
        int nr_coloane;

    protected:
    private:
        ull **m;
};

Matrice::Matrice() {}

Matrice::Matrice(int nl, int nc)
{
    nr_linii = nl;
    nr_coloane = nc;

    m = new ull*[nr_linii];
    for(int i = 0; i < nr_linii; i++)
    {
        m[i] = new ull[nr_coloane];
    }
}

Matrice::Matrice(const Matrice &mat)
{
    nr_linii = mat.nr_linii;
    nr_coloane = mat.nr_coloane;

    m = new ull*[nr_linii];
    for(int i = 0; i < nr_linii; i++)
    {
        m[i] = new ull[nr_coloane];
        for(int j = 0; j < nr_coloane; j++)
        {
            m[i][j] = mat.m[i][j];
        }
    }
}

Matrice::~Matrice()
{
    for(int i = 0; i < nr_linii; i++)
    {
       delete m[nr_coloane];
    }

    delete m;
}

ull Matrice::getValue(int l, int c)
{
    if(l >= 0 && l < nr_linii && c >= 0 && c < nr_coloane)
    {
        return m[l][c];
    }
    return m[0][0];
}

void Matrice::setValue(int l, int c, ull value)
{
    if(l >= 0 && l < nr_linii && c >= 0 && c < nr_coloane)
    {
        m[l][c] = value;
    }
}

bool Matrice::isSquare()
{
    return nr_linii == nr_coloane;
}


Matrice operator+(Matrice m1, Matrice m2)
{
    Matrice rezultat(m1.nr_linii, m1.nr_coloane);
    if(m1.nr_linii == m2.nr_linii && m1.nr_coloane == m2.nr_coloane)
    {
        for(int i = 0; i < m1.nr_linii; i++)
        {
            for(int j = 0; j < m1.nr_coloane; j++)
            {
                rezultat.setValue(i, j, m1.getValue(i, j) + m2.getValue(i, j));
            }
        }
    }
    return rezultat;
}


void Matrice::modul(ull v)
{
    for(int i = 0; i < nr_linii; i++)
    {
        for(int j = 0; j < nr_coloane; j++)
        {
            m[i][j] = m[i][j] % v;
        }
    }
}

Matrice operator-(Matrice m1, Matrice m2)
{
    Matrice rezultat(m1.nr_linii, m1.nr_coloane);
    if(m1.nr_linii == m2.nr_linii && m1.nr_coloane == m2.nr_coloane)
    {
        for(int i = 0; i < m1.nr_linii; i++)
        {
            for(int j = 0; j < m1.nr_coloane; j++)
            {
                rezultat.setValue(i, j, m1.getValue(i, j) - m2.getValue(i, j));
            }
        }
    }
    return rezultat;
}


Matrice operator*(Matrice m1, Matrice m2)
{
    Matrice rezultat(m1.nr_linii, m2.nr_coloane);
    for(int i = 0; i < m1.nr_linii; i++)
    {
        for(int j = 0; j < m1.nr_coloane; j++)
        {
            int sum = 0;
            for(int k = 0; k < m1.nr_coloane; k++)
            {
                sum += ((m1.getValue(i, k) % MOD) 
                * (m2.getValue(k, j) % MOD)) % MOD;
            }
            rezultat.setValue(i, j, sum);
        }
    }
    return rezultat;
}

void Matrice::print()
{
    for(int i = 0; i < nr_linii; i++)
    {
        for(int j = 0; j < nr_coloane; j++)
        {
            cout << getValue(i, j) << " ";
        }
    }
}

Matrice Matrice::operator=(Matrice mp)
{
    nr_linii = mp.nr_linii;
    nr_coloane = mp.nr_coloane;

    for(int i = 0; i < nr_linii; i++)
    {
        for(int j = 0; j < nr_coloane; j++)
        {
            m[i][j] = mp.m[i][j];
        }
    }
    return *this;
}

ifstream in ("kfib.in");
ofstream out ("kfib.out");


Matrice m_toPower(int p, Matrice par)
{
    if(p == 1) {
        return par;
    } else if (p % 2 == 1){
        Matrice m2 = m_toPower((p - 1) / 2, par);
        return par * m2 * m2;
    } else if (p % 2 == 0){
        Matrice m2 = m_toPower(p / 2, par);
        return m2 * m2;
    }
    
    return par;
}

int main()
{
	int k;
	in >> k;	
	
    Matrice Z(2, 2);
    Z.setValue(0, 0, 0);
    Z.setValue(0, 1, 1);
    Z.setValue(1, 0, 1);
    Z.setValue(1, 1, 1);

    Matrice Zk = m_toPower(k, Z);
        
    Matrice M1(1, 2);
    M1.setValue(0, 0, 0);
    M1.setValue(0, 1, 1);
    
    Matrice R = M1 * Zk;
   // R.print()  
    out << R.getValue(0, 0);
//    cout << "Raspuns final = " << R.getValue(0, 0);
    
    in.close();
    out.close();

    return 0;
}