#include <stdio.h>

#define M 	666013

FILE *fin;
FILE *fout;

unsigned long long N;
unsigned long long A[120];
unsigned long long An[4];
unsigned long long result;

void read(void) {
	fin = fopen("kfib.in", "r");
	fscanf(fin, "%llu", &N);
	fclose(fin);

	/* Init matrix */
	A[0] = 0;
	A[1] = 1;
	A[2] = 1;
	A[3] = 1;
}

void mul_An_with_power(unsigned long long i) {

	unsigned long long a0 = (An[0] * A[4*i]) % M + (An[1] * A[4*i+2]) % M;
	unsigned long long a1 = (An[0] * A[4*i+1]) % M + (An[1] * A[4*i+3]) % M;
	unsigned long long a2 = (An[2] * A[4*i]) % M + (An[3] * A[4*i+2]) % M;
	unsigned long long a3 = (An[2] * A[4*i+1]) % M + (An[3] * A[4*i+3]) % M;
	
	An[0] = a0 % M;
	An[1] = a1 % M;
	An[2] = a2 % M;
	An[3] = a3 % M;
}

void fibonacci(void) {
	unsigned long long logN = 0, cN, i;

	if (N <= 1) {
		result = N;
		return;
	}

	N--;
	cN = (N >> 1);

	while (cN != 0) {
		logN++;
		cN = (cN >> 1);
	}

	unsigned long long temp0, temp1, temp2, temp3;

	for (i = 1; i <= logN; i++) {
		temp0 = (A[4*(i-1)] * A[4*(i-1)]) % M;
		temp1 = (A[4*(i-1)+1] * A[4*(i-1)+2]) % M;
		temp2 = (A[4*(i-1)] + A[4*(i-1)+3]) % M;
		temp3 = (A[4*(i-1)+3] * A[4*(i-1)+3]) % M;

		A[4*i] = temp0 + temp1; 
		A[4*i+1] = (A[4*(i-1)+1] % M) * temp2;
		A[4*i+2] = (A[4*(i-1)+2] % M) * temp2;
		A[4*i+3] = temp3 + temp1;

		A[4*i] %= M;
		A[4*i+1] %= M;
		A[4*i+2] %= M;
		A[4*i+3] %= M;
	}

	An[0] = A[4*logN];
	An[1] = A[4*logN+1];
	An[2] = A[4*logN+2];
	An[3] = A[4*logN+3];

	for (i = 0; i < logN; i++) {
		if (N & (1 << i)) {
			mul_An_with_power(i);
		}
	}

	result = An[3];
}

void write(void) {
	fout = fopen("kfib.out", "w");
	fprintf(fout, "%llu", result);
	fclose(fout);
}

int main(void) {

	read();
	fibonacci();
	write();

	return 0;
}