#include <iostream>
#include <fstream>

using namespace std;

long long MOD = 666013;

long long** getMatrix(){
	long long **result;
	result = new long long*[2];
	result[0] = new long long[2];
	result[1] = new long long[2];
	result[0][0] = 0;
	result[0][1] = 1;
	result[1][0] = 1;
	result[1][1] = 1;
	return result;
}

long long** getIdentity(){
	long long **result;
	result = new long long*[2];
	result[0] = new long long[2];
	result[1] = new long long[2];
	result[0][0] = 1;
	result[0][1] = 0;
	result[1][0] = 0;
	result[1][1] = 1;
	return result;
}

long long** multiply(long long** A, long long** B){
	long long** result;
	result = new long long*[2];
	result[0] = new long long[2];
	result[1] = new long long[2];
	result[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
	result[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
	result[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
	result[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
	return result;
}

void free(long long **A){
	delete [] A[0];
	delete [] A[1];
	delete [] A;
}

long long** power(long long n){
	if (n == 0)
		return getIdentity();
	else if (n == 1)
		return getMatrix();
	else {
		long long **result, **partial, **A = power(n/2), **matrix = getMatrix();
		partial = multiply(A, A);
		if (n % 2 == 1){
			result = multiply(partial, matrix);
			free(partial);
		} else {
			result = partial;
		}

		free(A);
		free(matrix);

		return result;
	}
}

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

int main() {
	long long n;
	f >> n;
	long long **result = power(n - 1);
	g << result[1][1];
	free(result);
	f.close();
	g.close();
	return 0;
}