#include <vector>
#include <fstream>
	
 
	
using namespace std;
	
 
	
ifstream fin ("kfib.in");
	
ofstream fout ("kfib.out");
	
 
	
 
	
using ll = long long;
	
using VI = vector < ll > ;
	
using Matrix = vector < VI >;
	
 
	
const ll  mod = 666013;
	
const int k = 2;
	
 
	
Matrix T;
	
Matrix mult( Matrix A, Matrix B);
	
Matrix pow(Matrix A, int n);
	
int Fib(int n);
	
 
	
int main() {
	
	
	
	int n;
	
	fin >> n;
	
	fout << Fib(n);
	
}
	
 
	
Matrix mult( Matrix A, Matrix B) {
	
	
	
	Matrix res ( k + 1, VI ( k+ 1 )) ;
	
	for ( int i = 1; i <= k ; ++i)
	
		for ( int j = 1; j <= k ; ++j)
	
			for ( int w = 1; w <= k; ++w)
	
				res[i][j] = (res[i][j] + A[i][w] * B[w][j] ) % mod;
	
	return res;
	
}
	
 
	
Matrix pow(Matrix A, int p) {
	
	
	
	if ( p == 1)
	
		return A;
	
	if ( p & 1 )
	
		return mult(A,pow(A,p-1));
	
	Matrix X = pow(A,p/2);
	
	return mult(X,X);	
	
}
	
 
	
int Fib(int n) {
	
	
	
	VI F1(k+1);
	
	F1[1] = 1;
	
	F1[2] = 1;
	
	T = Matrix(k+1, vector <ll> (k+ 1) );
	
	T[1][1] = 0, T[1][2] = 1;
	
	T[2][1] = 1, T[2][2] = 1;
	
	if ( n == 1)
	
		return 1;
	
	T = pow(T,n-1);
	
	ll res = 0;
	
	for ( int i = 1; i <= k; ++i)
	
		res = ( res + T[1][i] * F1[i]) % mod;
	
	return res;
	
	
	
}