#include <cstring>
#include <cstdio>
#include <cmath>

long long k;
long long m = 666013;

struct Mat {
	long long a, b, c, d;
	void sqr() {
		int an = (a * a + b * c) % m;
		int bn = (a * b + b * d) % m;
		int cn = (c * a + d * c) % m;
		int dn = (c * b + d * d) % m;
		a = an;
		b = bn;
		c = cn;
		d = dn;
	}
	void mult(long long & x, long long & y) {
		int xn = a * x + b * y;
		int yn = c * x + d * y;
		x = xn;
		y = yn;
	}
};

Mat fib;

int main() {
	fib.a = 0;
	fib.b = 1;
	fib.c = 1;
	fib.d = 1;
	FILE * in = fopen("kfib.in", "rt");
	FILE * out = fopen("kfib.out", "wt");

	fscanf(in, "%d", &k);

	long long a = 0;
	long long b = 1;

	for (int i = 0; i < 32; ++i) {
		if (k & (1 << i)) {
			fib.mult(a, b);
		}
		fib.sqr();
	}
	fprintf(out, "%lld\n", a);

	fclose(in);
	fclose(out);
}