#include <stdio.h>
#define M 666013

int** prod(int a[2][2], int b[2][2]) {
	int res[2][2];
	res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % M;
	res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % M;
	res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % M;
	res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % M;
	
	return res;
}

int** put(int n[2][2], int p) {
	if(p == 0) {
		int res[2][2] = {{1, 0}, {0, 1}};
		return res;
	}
	int[2][2] res = (*prod(put(n, p/2), put(n, p/2)))[2];
	if(p % 2 == 1) {
		res = (*prod(res, n))[2];
	}
	return res;
}

int main() {
	FILE* fin = fopen("kfib.in", "r");
	int k;
	fscanf(fin, "%d\n", &k);
	fclose(fin);
	
	int tab[2][2] = {{0, 1}, {1, 1}};
	FILE* fout = fopen("kfib.out", "w");
	int res;
	if(k == 0) {
		res = 0;
	} else {
		int mult[2][2] = (*put(tab, k - 1))[2]; 
		res = mult[1][1];
	}
	
	fprintf(fout, "%d\n", res);
	fclose(fout);
	return 0;
}