#include <iostream>
#include <fstream>
#include <cstring>

const char IN[] = "kfib.in", OUT[] = "kfib.out";

int K;
const int MODULO = 666013;

inline void read_data() {
	fscanf(fopen(IN, "r"), "%d", &K);
}

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

inline void mul(int A[][2], int B[][2], int C[][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;
}

void lgPow(int B[2][2], int p) {
	if (p == 0) {
		B[0][0] = 1; B[0][1] = 0;
		B[1][0] = 0; B[1][1] = 1;
		return;
	}
	if (p == 1) return;
	if (p % 2 == 0) {
		int AUX[2][2];
		memcpy(AUX, B, sizeof(AUX));
		lgPow(AUX, p / 2);
		mul(AUX, AUX, B);
		return;
	}
	else {
		int AUX[2][2], C[2][2];
		memcpy(AUX, B, sizeof(AUX));
		lgPow(AUX, p / 2);
		mul(AUX, AUX, C);
		mul(C, CT, B);		
	}
}

int kfibo(int k){
	if (k == 0) return 0;
	if (k == 1 || k == 2) return 1;
	int C[2][2];
	memcpy(C, CT, sizeof(C));
	lgPow(C, k-2);
	return (C[0][1] + C[1][1]) % MODULO;
}

int main() {
	read_data();
	fprintf(fopen(OUT, "w"), "%d\n", kfibo(K));
	return 0;
}