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

using namespace std;
typedef int Matrix[2][2];
inline void Multiply( Matrix X, Matrix Y )
{
	int i, j, k;
	Matrix R={ { 0, 0 }, { 0, 0 } };
	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*X[i][k]*Y[k][j])%MODULO )%MODULO;
		}
	for( i=0; i < 2; ++i )
		for( j=0; j < 2; ++j )
			X[i][j]=R[i][j];
}
inline int pow( int n )
{
	Matrix F={ { 1, 1 }, { 1, 0 } }, R={ { 1, 0 }, { 0, 1 } };
	for( ; n; n>>=1 )
	{
		if( n&1 )
		{
			Multiply( R, F );
			--n;
		}
		Multiply( F, F );
	}
	return R[0][0];
}
int main( void )
{
	int K;
	ifstream in( "kfib.in" );
	in>>K;
	ofstream out( "kfib.out" );
	out<<pow( K-1 )<<'\n';
	return EXIT_SUCCESS;
}