//      kfib.cpp
//
//      Copyright 2010 SpeeDemon <virtualdemon@ubuntu>
//
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of the GNU General Public License as published by
//      the Free Software Foundation; either version 2 of the License, or
//      (at your option) any later version.
//
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.
//
//      You should have received a copy of the GNU General Public License
//      along with this program; if not, write to the Free Software
//      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
//      MA 02110-1301, USA.
#include <cstdio>
#include <cstdlib>
#define Modulo  666013

/*
 *
 */
using namespace std;
int F[2][2], R[2][2];
inline void f( int X[2][2], int Y[2][2] )
{
    int R[2][2];
    R[0][0]=( (1LL*X[0][0]*Y[0][0] ) + (1LL*X[0][1] * Y[1][0] ) )%Modulo;
    R[0][1]=( (1LL*X[0][0]*Y[0][1] ) + (1LL*X[0][1] * Y[1][1] ) )%Modulo;
    R[1][0]=( (1LL*X[1][0]*Y[0][0] ) + (1LL*X[1][1] * Y[1][0] ) )%Modulo;
    R[1][1]=( (1LL*X[1][0]*Y[0][1] ) + (1LL*X[1][1] * Y[1][1] ) )%Modulo;
    X[0][0]=R[0][0]; X[0][1]=R[0][1];
    X[1][0]=R[1][0]; X[1][1]=R[1][1];
}
inline void pow( int N )
{
	for( ; N; N>>=1 )
	{
		if( N&1 )
		{
			f( R, F );
			--N;
		}
		f( F, F );
	}
}
int main( void )
{
	int N;
	fscanf( fopen( "kfib.in", "rt" ), "%d", &N );
        F[0][0]=F[0][1]=F[1][0]=R[0][0]=R[1][1]=1;
	pow( N-1 );
	fprintf( fopen( "kfib.out", "wt" ), "%d", R[0][0] );
	return EXIT_SUCCESS;
}