#include <stdio.h>
#define M 666013

int** prod(int** a, int** b) {
	int** res;
	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, int p) {
	if(p == 0) {
		int** res = {{1, 0}, {0, 1}};
		return res;
	}
	int** res = prod(put(n, p/2), put(n, p/2));
	if(p % 2 == 1) {
		res = prod(res, n);
	}
	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 = put(tab, k - 1); 
		res = mult[1][1];
	}
	
	fprintf(fout, "%d\n", res);
	fclose(fout);
	return 0;
}