#include <fstream>

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

const long long mod = 666013;

struct matrice	{
	long long a, b, c, d;
} a, b;

matrice inmultire(matrice x, matrice y)	 {
	matrice aux;
	aux.a = (x.a * y.a + x.b * y.c) % mod;
	aux.b = (x.a * y.b + x.b * y.d) % mod;
	aux.c = (x.c * y.a + x.d * y.c) % mod;
	aux.d = (x.c * y.b + x.d * y.d) % mod;
	return aux;
}

matrice lgput(matrice a, long long e)	 {
	if (e == 0)
		return {1, 0, 0, 1};
	matrice aux = {1, 0, 0, 1};
	if (e & 1)
		aux = {0, 1, 1, 1};
	matrice ans = lgput(a, e / 2);
	ans = inmultire(ans, ans);
	return inmultire(ans, aux);
}

int main() {
	long long n;
	fin >> n;
	if (n == 0)	 {
		fout << 0;
		return 0;
	}
	if (n <= 2)	 {
		fout << 1;
		return 0;
	}
	a = {0, 1, 1, 1};
	a = lgput(a, n - 2);
	fout << (a.b + a.d) % mod;
	return 0;
}