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

#define MOD 666013

struct matrix {
	long long lu, ru, ld, rd;
};

void print_matrix(struct matrix *matrix)
{
	printf("%lld %lld\n", matrix->lu, matrix->ru);
	printf("%lld %lld\n\n", matrix->ld, matrix->rd);
}

void multiply_matrix(struct matrix *matrix1, struct matrix *matrix2)
{
	struct matrix tmp_matrix;

	tmp_matrix.lu = (matrix1->lu * matrix2->lu + matrix1->ru * matrix2->ld) % MOD;
	tmp_matrix.ru = (matrix1->lu * matrix2->ru + matrix1->ru * matrix2->rd) % MOD;
	tmp_matrix.ld = (matrix1->ld * matrix2->lu + matrix1->rd * matrix2->ld) % MOD;
	tmp_matrix.rd = (matrix1->ld * matrix2->ru + matrix1->rd * matrix2->rd) % MOD;

	memcpy(matrix1, &tmp_matrix, sizeof(struct matrix));
}

void matrix_pow(struct matrix *matrix, long long n)
{
	struct matrix tmp_matrix;
	memcpy(&tmp_matrix, matrix, sizeof(struct matrix));

	if (n == 1)
		return;

	matrix_pow(matrix, n >> 1);

	multiply_matrix(matrix, matrix);
	if (n & 1)
		multiply_matrix(matrix, &tmp_matrix);
}

long long fib(long long n)
{
	struct matrix matrix = {
		.lu = 0, .ru = 1,
		.ld = 1, .rd = 1,
	};

	if(n == 0)
		return 0;

	matrix_pow(&matrix, n);

	return (matrix.lu + matrix.ld) % MOD;
}

int main()
{
	long long n;

	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	scanf("%lld", &n);

	printf("%lld\n", fib(n - 1));

	return 0;
}