#include <stdio.h>
#include <math.h>

long n;
long long rez[3][3], put[3][3];

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

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	
	scanf("%ld", &n);
	
	put[1][1] = 0, put[1][2] = 1, put[2][1] = 1, put[2][2] = 1;
	rez[1][1] = 1, rez[1][2] = 0, rez[2][1] = 0, rez[2][2] = 1;
	
	while (n != 0) {
		if (n % 2 == 1)
			mul(rez, put);
		mul(put, put);
		n /= 2;
	}
	
	printf("%lld\n", rez[2][1]);
	
	return 0;
}