#include <stdio.h>
#define MAX 30
#define R 666013
#define ll long long

typedef struct{
	ll a, b, c, d;
} mat;

ll k;
mat v[MAX], m;

mat matmult(mat x, mat y;);
void kfib(ll k);

int main(){
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%lld", &k);
	m.a = m.d= 1, m.b = m.c = 0;
	v[0].a = 0, v[0].b = v[0].c = v[0].d = 1;
	kfib(k);
	return 0;
}

mat matmult(mat x, mat y){
	mat z;
	z.a = (x.a * y.a + x.b * y.c) % R;
	z.b = (x.a * y.b + x.b * y.d) % R;
	z.c = (x.c * y.a + x.d * y.c) % R;
	z.d = (x.c * y.b + x.d * y.d) % R;
	return z;
}

void kfib(ll k){
	if(k == 0){
		printf("0");
		return;
	}
	if(k == 1){
		printf("1");
	 	return;
	}

	ll aux = k - 1;
	int nr = 0;
	while(aux > 1){
		aux /= 2;
		v[++nr] = matmult(v[nr - 1], v[nr - 1]);
	}

	m = matmult(m, v[nr]);
	k -= 1<<nr;
	while(k > 1){
		nr = 0;
		aux = k - 1;
		while(aux > 1){
			aux /= 2;
			++nr;
		}

		m = matmult(m, v[nr]);
		k -= 1<<nr;
	}

	printf("%lld", m.d);
}