#include <cstdio>
#include <utility>
using namespace std;

FILE *f = fopen ( "kfib.in" , "r" ) , *g = fopen ("kfib.out" , "w" );
const int MOD = 666013;
int K;

void multiply ( pair <long long,long long> &x , long long mult[2][2] )
{
	pair <long long,long long> y = x;
	x.first = ( y.first * mult[0][0] + y.second * mult[1][0] ) % MOD;
	x.second = ( y.first * mult[0][1] + y.second * mult[1][1] ) % MOD;
}

void multiplyMatrix ( long long x[2][2] , long long y[2][2] )
{
    long long aux[2][2];
    aux[0][0] = ( x[0][0] * y[0][0] + x[0][1] * y[1][0] ) % MOD;
    aux[0][1] = ( x[0][0] * y[0][1] + x[0][1] * y[1][1] ) % MOD;
    aux[1][0] = ( x[1][0] * y[0][0] + x[1][1] * y[1][0] ) % MOD;
    aux[1][1] = ( x[1][0] * y[0][1] + x[1][1] * y[1][1] ) % MOD;
    x[0][0] = aux[0][0] , x[0][1] = aux[0][1] , x[1][0] = aux[1][0] , x[1][1] = aux[1][1];
}

long long getFibK ( int nrSteps )
{
	pair <long long,long long> solution = make_pair(0,1);
	long long aux[2][2] = {{0,1},{1,1}};
	while ( nrSteps )
	{
		if ( nrSteps % 2 == 1 )
			multiply ( solution , aux );
		multiplyMatrix ( aux , aux );
		nrSteps /= 2;
	}
	return solution.first;
}

int main()
{
	//read K
	fscanf ( f , "%d" , &K );
	fprintf ( g , "%lld\n" , getFibK ( K ) );
	return 0;
}