#include <fstream>
#include <cstring>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const int MOD = 666013;

class AATROX {
	public:
		int a[3][3];
		///  Constructori
		AATROX() {
			memset(a, 0, sizeof(a) );
		}
		void operator *=(const AATROX &B);
};

void AATROX :: operator *=(const AATROX &B) {
	AATROX C;
	for( int i= 1; i<3; ++i ) {
		for( int j= 1; j<3; ++j ) {
			for( int k= 1;  k<3;  ++k )
				C.a[i][j]= ( C.a[i][j]+ 1LL*a[i][k]*B.a[k][j] ) % MOD;
		}
	}
	*this= C;
}

void lgput( AATROX &A, int b ) {
	AATROX R;
	R.a[1][1]= R.a[2][2]= 1;
	while( b ) {
		if( b&1 ) {
			R*= A;
		}
		A*= A;
		b>>= 1;
	}
	A= R;
}

int main() {
	int N;
	in >> N;
	AATROX A;
	A.a[1][1]= A.a[1][2]= A.a[2][1]= 1;

	if( N == 0 ) { out << "0\n"; return 0; }
	else if( N == 1 ) { out << "1\n"; return 0; }

	lgput( A, N-1 );
	out << A.a[1][1] << '\n';

	return 0;
}