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



	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;

}