#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;
	
}