#include <cstdio>

const int MOD(666013);

int k, kth;

inline void read (void)
{
	std::freopen("kfib.in","r",stdin);
	std::scanf("%d",&k);
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("kfib.out","w",stdout);
	std::printf("%d\n",kth);
	std::fclose(stdout);
}

inline void mul (int a [2] [2], int b [2] [2])
{
	int aux [2] [2] = {{0}};
	int i, j, k;
	for (i = 0 ; i < 2 ; ++i)
		for (j = 0 ; j < 2 ; ++j)
		{
			for (k = 0 ; k < 2 ; ++k)
				aux[i][j] += (static_cast<long long>(a[i][k]) * b[k][j]) % MOD;
			aux[i][j] %= MOD;
		}
	a[0][0] = aux[0][0];
	a[0][1] = aux[0][1];
	a[1][0] = aux[1][0];
	a[1][1] = aux[1][1];
}

inline void pow (int matrix [2] [2], int exponent)
{
	int result [2] [2] = {
						 {1,0},
						 {0,1}
						 };
	int aux [2] [2];
	aux[0][0] = matrix[0][0];
	aux[0][1] = matrix[0][1];
	aux[1][0] = matrix[1][0];
	aux[1][1] = matrix[1][1];
	while (exponent)
	{
		if (exponent & 0x01)
			mul(result,aux);
		mul(aux,aux);
		exponent >>= 1;
	}
	matrix[0][0] = result[0][0];
	matrix[0][1] = result[0][1];
	matrix[1][0] = result[1][0];
	matrix[1][1] = result[1][1];
}

inline void compute (void)
{
	if (k)
	{
		int matrix [2] [2] = {
							 {0,1},
							 {1,1}
							 };
		pow(matrix,k - 1);
		kth = matrix[1][1];
	}
}

int main (void)
{
	read();
	compute();
	print();
	return 0;
}