#include <iostream>
#include <fstream>

using namespace std;

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

#define mod 666013

int SOLUTIE[3][3];
int Z[3][3];

/*
Explicatii:
La pasul n vom avea deja calculate F(n-2) si F(n-1) si vom dori sa il aflam pe F(n)

( F(n-2) F(n-1) ) * ( 0 1 ) = ( F(n-1) F(n) )
                    ( 1 1 )

Z = matricea constanta de mai sus

M(i) = ( F(i-1) F(i) )

M(i) = M(i-1) * Z       |  => M(i) = M(i-2) * Z^2
M(i-1) = M(i-2) * Z     |

Prin inductie => M(i) = M(1) * Z^(i-1)
*/


/*
Functie ajutatoare care realizeaza inmultire dintre doua matrici si returneaza rezultatul in matricea AUX
*/
void inmultireMAT(int A[][3], int B[][3], int AUX[][3])
{
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                AUX[i][j] = (AUX[i][j] + 1LL * A[i][k] * B[k][j]) % mod;
}
/*
Functie ajutatoare care copiaza continutul unei matrici B intr-o matrice A
*/
void copyMAT(int A[][3], int B[][3])
{
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            A[i][j] = B[i][j];
}
/*
Functie ajutatoare care goleste o matrice data ca parametru
*/
void emptyMAT(int A[][3])
{
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            A[i][j] = 0;
}

/*
Functie care face ridicarea la putere in timp logaritmic pe matrici
O folosesc pentru a ridica matricea Z la puterea n-1;
*/
void lg_power(int p,int M[][3])
{
    int C[3][3], AUX[3][3], i;

    copyMAT(C,Z);

    M[0][0] = M[1][1] = 1;


    for(i = 0; (1<<i)<=p; i++)
    {
        if(p & (1 << i))
        {
            emptyMAT(AUX);
            inmultireMAT(M,C,AUX);
            copyMAT(M,AUX);

        }
        emptyMAT(AUX);
        inmultireMAT(C,C,AUX);
        copyMAT(C,AUX);
    }

}

int main()
{
	int n;
	in>>n;
	/*in matricea Z avem constanta de a ajunge la un element i folosind elementele i-2 si i-1
	Z:   0 1
	     1 1
    */


    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][0] = 1;
    Z[1][1] = 1;

	lg_power(n-1,SOLUTIE);

	out<<SOLUTIE[1][1];

}