#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MODULO 666013

int sol[2][2] = { {1, 0}, {0, 1} };

void multiply(int a[2][2], int b[2][2]) {

	int c[2][2];

	c[0][0] = ((1LL * a[0][0] * b[0][0]) % MODULO + (1LL * a[0][1] * b[1][0]) % MODULO) % MODULO;
	c[0][1] = ((1LL * a[0][0] * b[0][1]) % MODULO + (1LL * a[0][1] * b[1][1]) % MODULO) % MODULO;
	c[1][0] = ((1LL * a[1][0] * b[0][0]) % MODULO + (1LL * a[1][1] * b[1][0]) % MODULO) % MODULO;
	c[1][1] = ((1LL * a[1][0] * b[0][1]) % MODULO + (1LL * a[1][1] * b[1][1]) % MODULO) % MODULO;

	for (int i = 0; i < 2; i++) {

		for (int j = 0; j < 2; j++) {

			a[i][j] = c[i][j];
		}
	}
}

void n_fibonacci(int n) {

	int a[2][2] = { {1, 1}, {1, 0} };

	while (n > 0) {

		if (n % 2 == 1) {

			multiply(sol, a);
		}

		multiply(a, a);

		n /= 2;
	}
}

int main() {

	FILE* ip;
	ip = fopen("kfib.in", "r");
	if (ip == NULL) {

		perror("Cannot open input file");
		return 1;
	}

	FILE* op;
	op = fopen("kfib.out", "w");
	if (op == NULL) {

		perror("Cannot open output file");
		return 1;
	}

	int k;
	fscanf(ip, "%d", &k);

	if (k == 0) {

		fprintf(op, "%d", 0);
	}
	else {

		n_fibonacci(k - 1);

		fprintf(op, "%d", sol[0][0] % MODULO);
	}

	fclose(ip);
	fclose(op);

	return 0;
}