#include <stdio.h>
#define M 666013

typedef struct matrice {
	long long t[2][2];
} mat;


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

mat put(mat n, int p) {
	if(p == 0) {
		mat res;
		res.t[0][0] = 1;
		res.t[0][1] = 0;
		res.t[1][0] = 0;
		res.t[1][1] = 1;
		return res;
	}
	if(p == 1) {
		return n;
	}
	mat inter = put(n, p/2);
	mat res = prod(inter, inter);
	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);
	
	mat tab;
	tab.t[0][0] = 0;
	tab.t[0][1] = 1;
	tab.t[1][0] = 1;
	tab.t[1][1] = 1;
	
	int res;
	if(k == 0) {
		res = 0;
	} else {
		mat mult = put(tab, k - 1); 
		res = mult.t[1][1];
	}
	FILE* fout = fopen("kfib.out", "w");
	fprintf(fout, "%d\n", res);
	fclose(fout);
	return 0;
}