#include <stdio.h>
#define MOD 666013


long long K, p[2][2], a[2][2];
void mul(long long a[2][2], long long b[2][2], long long c[2][2]) {
	long long r[2][2];
	r[0][0] = a[0][0]*b[0][0] % MOD + a[0][1]*b[1][0] % MOD ;
	r[0][1] = a[0][0]*b[0][1] % MOD + a[0][1]*b[1][1] % MOD ;
	r[1][0] = a[1][0]*b[0][0] % MOD + a[1][1]*b[1][0] % MOD ;
	r[1][1] = a[1][0]*b[0][1] % MOD + a[1][1]*b[1][1] % MOD ;
	c[0][0] = r[0][0] % MOD;
	c[0][1] = r[0][1] % MOD;
	c[1][0] = r[1][0] % MOD;
	c[1][1] = r[1][1] % MOD;
}

int main () {
	FILE *f = fopen("kfib.in","r");
	FILE *g = fopen("kfib.out","w");
	fscanf(f,"%lld",&K);
	fclose(f);
	K--;

	p[0][0] = p[1][1] = 1;
	p[1][0] = p[0][1] = 0;
	a[0][0] = 0;
	a[0][1] = a[1][0] = a[1][1] = 1;
	while (K) {
		if (K%2 == 1) {
			//p = p*a;
			mul(p,a,p);
		}
		//a = a*a;
		mul(a,a,a);
		K = K/2;
	}
	
	fprintf(g,"%lld",p[1][1]);
	return 0;
}