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

using namespace std;
typedef unsigned int uint;
typedef uint Mat[2][2];
typedef unsigned long long int uint64;
inline void Multiply( Mat A, Mat B )
{
	Mat R={ { 0, 0 }, { 0, 0 } };
	uint i, j, k;
	for( i=0; i < 2; ++i )
		for( j=0; j < 2; ++j )
			for( k=0; k < 2; ++k )
				R[i][j]=( R[i][j]+1LL*A[i][k]*B[k][j] )%MODULO;
	for( i=0; i < 2; ++i )
		for( j=0; j < 2; ++j )
			A[i][j]=R[i][j];
}
inline uint Fibonacci( uint n )
{
	if( 0 == n )
		return 0;
	if( n <= 2 )
		return 1;
	Mat F={ { 1, 1 }, { 1, 0 } }, R={ { 1, 0 }, { 0, 1 } };
	for( n-=1; n; n>>=1 )
	{
		if( n&1 )
		{
			Multiply( R, F );
			--n;
		}
		Multiply( F, F );
	}
	return R[0][0];
}
int main( void )
{
	uint k;
	ifstream in( "kfib.in" );
	in>>k;
	ofstream out( "kfib.out" );
	out<<Fibonacci( k )<<'\n';
	return EXIT_SUCCESS;
}