#include <stdio.h>
#include <string.h>

unsigned int M[2][2] = {{0, 1}, {1, 1}};
unsigned int S[2][2] = {{1, 0}, {0, 1}};

void multiply (unsigned int C[][2], unsigned int A[][2], unsigned int B[][2]) {	
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				C[i][j] += ((long long) A[i][k]) * B[k][j] % 666013;
			}
		}
	}
}

void computeS (int k) {
	int mask = 1;
	while (mask <= k) {
		if (k & mask) {
			unsigned int temp[2][2] = {{0}};
			multiply(temp, S, M);
			memcpy(S, temp, 4 * sizeof(unsigned int));
		}
		
		unsigned int temp[2][2] = {{0}};
		multiply(temp, M, M);
		memcpy(M, temp, 4 * sizeof(unsigned int));
		
		mask <<= 1;
	}
}

int main (void) {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	
	int k;
	scanf("%d", &k);
	
	computeS(k-1);
	
	printf("%d", S[1][1]);
	
	return 0;
}