#include <fstream>
#include <vector>
using namespace std;
#define MOD 666013
vector <vector <int>> produs( vector <vector <int>> a, vector <vector <int>> b ){
	vector <vector <int>> r( a.size(), vector <int>( b[0].size() ) );
	int i, j, k;
	for( i = 0; i < a.size(); i++ ){
		for( j = 0; j < b[0].size(); j++ ){
			for( k = 0; k < b.size(); k++ ){
				r[i][j] = ( r[i][j] + 1ll * a[i][k] * b[k][j] ) % MOD;
			}
		}
	}
	return r;
}
vector <vector <int>> putere( vector <vector <int>> &x, int e ){
	vector <vector <int>> a;
	if( e == 0 ){
		return { { 1, 0 },
				 { 0, 1 } };
	}
	a = putere( x, e / 2 );
	if( e % 2 == 0 ){
		return produs( a, a );
	}
	return produs( produs( a, a ), x );
}
int main(){
	int k;
	ifstream fin( "kfib.in" );
	ofstream fout( "kfib.out" );
	fin >> k;
	vector <vector <int>> a, x;
	a = { { 0, 1 } };
	x = { { 0, 1 },
		  { 1, 1 } };
	x = putere( x, k );
	a = produs( a, x );
	fout << a[0][0];
	return 0;
}