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

using namespace std;
typedef unsigned int Mat[2][2];
typedef unsigned long long int uint64;
Mat A, R, X;
inline uint64 gdc( uint64 a, uint64 b )
{
	uint64 r=b;
	while( b )
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}
inline void Multiply( Mat A, Mat B, Mat& R )
{
	R[0][0]=( 1LU*A[0][0]*B[0][0]+1LU*A[0][1]*B[1][0] )%MODULO;
	R[0][1]=( 1LU*A[0][0]*B[0][1]+1LU*A[0][1]*B[1][1] )%MODULO;
	R[1][0]=( 1LU*A[1][0]*B[0][0]+1LU*A[1][1]*B[1][0] )%MODULO;
	R[1][1]=( 1LU*A[1][0]*B[0][1]+1LU*A[1][1]*B[1][1] )%MODULO;
}
inline unsigned int fibonacci( int n )
{
	if( 0 == n )
		return 0;
	if( n <= 2 )
		return 1;
	n-=1;
	A[0][0]=A[0][1]=A[1][0]=R[0][0]=R[1][1]=1;
	for( ; n; n>>=1 )
	{
		if( n&1 )
		{
			Multiply( R, A, X );
			R[0][0]=X[0][0]; R[0][1]=X[0][1];
			R[1][0]=X[1][0]; R[1][1]=X[1][1];
			--n;
		}
		Multiply( A, A, X );
		A[0][0]=X[0][0]; A[0][1]=X[0][1];
		A[1][0]=X[1][0]; A[1][1]=X[1][1];
	}
	return R[0][0];
}
int main( void )
{
	int k;
	ifstream in( "kfib.in" );
	in>>k;
	ofstream out( "kfib.out" );
	out<<fibonacci( k )<<'\n';
	return EXIT_SUCCESS;
}