#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define infile "kfib.in"
#define outfile "kfib.out"

#define MAGIC 666013
#define DIM 2

FILE *fin, *fout;
long long z[DIM][DIM] = {0, 1, 1, 1}, res[DIM][DIM];

void matrix_multiply(long long a[DIM][DIM], long long b[DIM][DIM]) {

	int i, j, k, sum;
	long long c[DIM][DIM];

	for (i = 0; i < DIM; i++) {
		for (j = 0; j < DIM; j++) {
			sum = 0;
			for (k = 0; k < DIM; k++) {
				sum += ((a[i][k] * b[k][j]) % MAGIC);
			}
			c[i][j] = (sum%MAGIC);		
		}
	}
	memcpy(res, c, sizeof(res));
}


void matrix_pow(int p) {

	printf("%d\n", p);
	fflush(stdout);

	if (p == 0) {
		memset(res, 1, sizeof(res));
		return;
	}
	if (p == 1) {
		memcpy(res, z, sizeof(res));
		return;
	}

	if (p % 2 == 0) {
		matrix_pow(p / 2);
		matrix_multiply(res, res);
		return;
	}

	matrix_pow((p - 1)/2);
	matrix_multiply(res, res);
	matrix_multiply(res, z);
}

int main() {
	int k;
	fin = freopen(infile, "r", stdin);
	fout = freopen(outfile, "w", stdout);

	scanf("%d", &k);	
	
	if (k == 0) {
		printf("0\n");
		return 0;
	}

	matrix_pow(k - 1);
	printf("%lld\n", res[1][1]);

	return 0;
}