#include <stdio.h>
#include <assert.h>

const int MOD = 666013;
int kth_fib(int);

void redirect_io() {

	assert(freopen("kfib.in","r",stdin) != NULL);
	assert(freopen("kfib.out","w",stdout) != NULL);
	assert(freopen("kfib.err","w",stderr) != NULL);	
}

int main() {

	int K;
	redirect_io();
	assert(scanf("%d", &K) == 1);
	printf("%d\n", kth_fib(K));
	return 0;
}

void raise_to_pow(int [2][2], int);
void mult(int [2][2], int [2], int [2]);

int kth_fib(int K) {

	if(K == 0)
		return 0;
	if(K == 1)
		return 1;
	else {
		int A[2][2] = {{1, 1}, {1, 0}};
		int f0[2] = {1, 0};
		int f1[2] = {0, 0};
		raise_to_pow(A, K - 1);
		mult(A, f0, f1);
		return f1[0];
	}
}

/* warning: operation destructive on input */
void mult_mat(int a[2][2], int b[2][2]) {
	
	int tmp[2][2] = {{a[0][0], a[0][1]}, {a[1][0], a[1][1]}};
	int (*tmp2)[2] = (b == a ? tmp : b);
	
	int i,j,k;
	for(i = 0;i < 2;i ++)
		for (j = 0; j < 2; j++) {
			a[i][j] = 0;
			for(k = 0; k < 2;k ++)
				/* create long long temporary to store potential overflow */
				a[i][j] += ((long long)tmp[i][k] * tmp2[k][j]) % MOD;
		}
}

/* warning: operation destructive on input */
void raise_to_pow(int a[2][2], int K) {

	int tmp[2][2] = {{a[0][0], a[0][1]}, {a[1][0], a[1][1]}};
	a[0][0] = a[1][1] = 1; a[0][1] = a[1][0] = 0;

	while(K) {
		if(K % 2 == 1) {
			mult_mat(a, tmp);
		}
		K >>= 1;
		mult_mat(tmp,tmp);
	}
}

/* this could overflow in general however for this particular case it can't */
void mult(int a[2][2], int f0[2], int f1[2]) {

	int i,k;
	for(i = 0; i < 2; i++) {
		f1[i] = 0;
		for(k=0; k < 2; k++)
			f1[i] += a[i][k] * f0[k];
	}
}