#include <stdio.h>
#include <fstream>

#define MOD(x) ((x) % 666013)


long* mult( long* m1, long* m2 )
{
	long* res = new long[4];
	res[0] = MOD(MOD(m1[0]) * MOD(m2[0])) + MOD(MOD(m1[1]) * MOD(m2[2]));
	res[0] = MOD(res[0]);
	res[1] = MOD(MOD(m1[0]) * MOD(m2[1])) + MOD(MOD(m1[1]) * MOD(m2[3]));
	res[1] = MOD(res[1]);
	res[2] = MOD(MOD(m1[2]) * MOD(m2[0])) + MOD(MOD(m1[3]) * MOD(m2[2]));
	res[2] = MOD(res[2]);
	res[3] = MOD(MOD(m1[2]) * MOD(m2[1])) + MOD(MOD(m1[3]) * MOD(m2[3]));
	res[3] = MOD(res[3]);
	return res;
}

long* power( long* m, int p )
{
	if( p == 0 )
	{
		long* res = new long[4];
		res[0] = 1;
		res[1] = 0;
		res[2] = 0;
		res[3] = 1;
		return res;
	}

	long* res = power( m, p / 2 );
	long* res2 = mult( res, res );
	delete[] res;
	if( p % 2 )
	{
		long* res3 = mult( res2, m );
		delete[] res2;
		return res3;
	}
	else
	{
		return res2;
	}
}

int kfib( int n )
{
	if( n < 2 )
	{
		return n;
	}
	long test[] = { 0, 1, 1, 1 };
	return power( test, n-1 )[3];
}

void test()
{
	for( int i = 0; i < 30; ++i )
	{
		if( i % 8 == 0 && i > 0 )
		{
			printf("\n");
		}
		printf("%7d", kfib(i));
	}
	printf("\n");
}

void test2()
{
	printf( "%d\n", kfib(1024) );
}

void run()
{
	std::ofstream fout( "kfib.out" );
	std::ifstream fin( "kfib.in" );
	int n;
	fin >> n;
	fout << kfib( n );
}

int main()
{
	run();
	return 0;
}