#include <cstdlib>
#include <fstream>
#define Modulo 666013

/*
 *
 */
using namespace std;
typedef int Matrix[2][2];
Matrix Fn, X;
inline void multiply( Matrix A, Matrix B ) // A=A*B
{
    Matrix R;
    R[0][0]=( 1LL*A[0][0]*B[0][0]+1LL*A[0][1]*B[1][0] )%Modulo;
    R[0][1]=( 1LL*A[0][0]*B[0][1]+1LL*A[0][1]*B[1][1] )%Modulo;
    R[1][0]=( 1LL*A[1][0]*B[0][0]+1LL*A[1][1]*B[1][0] )%Modulo;
    R[1][1]=( 1LL*A[1][0]*B[0][1]+1LL*A[1][1]*B[1][1] )%Modulo;
    A[0][0]=R[0][0]; A[0][1]=R[0][1];
    A[1][0]=R[1][0]; A[1][1]=R[1][1];
}
inline void pow( int k ) // Fn^k
{
    Fn[1][1]=Fn[0][0]=1;
    X[0][0]=X[0][1]=X[1][0]=1;
    for( ; k; k>>=1 )
    {
        if( k&1 )
        {
            multiply( Fn, X );
            --k;
        }
        multiply( X, X );
    }
}
int main( void )
{
    int k;
    ifstream in( "kfib.in" );
    in>>k;
    pow( k-1 );
    ofstream out( "kfib.out" );
    out<<Fn[0][0]<<'\n';
    return EXIT_SUCCESS;
}