#include <fstream>
using namespace std;

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

const int MOD = 666013;
int n, a[1 << 2][1 << 2], b[1 << 2][1 << 2], v[1 << 2][1 << 2], aux[1 << 2][1 << 2];

void prod (int v[][1 << 2], int a[][1 << 2], int b[][1 << 2]) {
	for (int i = 1; i <= 2; ++i) {
		for (int j = 1; j <= 2; ++j) {
			v[i][j] = 0;
			for (int k = 1; k <= 2; ++k) {
				v[i][j] += a[i][k] * b[k][j];
				v[i][j] %= MOD;
			}
		}
	}
}

void copy (int a[][1 << 2], int b[][1 << 2]) {
	for (int i = 1; i <= 2; ++i) {
		for (int j = 1; j <= 2; ++j) {
			a[i][j] = b[i][j];
		}
	}
}

void init () {
	a[1][1] = a[1][2] = a[2][1] = 1;
	v[1][1] = v[1][2] = 1;
}

void exe () {
	for (; n; n >>= 1) {
		if (n & 1) {
			prod (aux, v, a);
			copy (v, aux);
		}
		prod (aux, a, a);
		copy (a, aux);
	}
}

void afisare () {
	out << v[1][1] % MOD;
}

void citire () {
	in >> n;
}

int main () {
	citire ();
	
	init ();
	
	exe ();
	
	afisare ();
	
	return 0;
}