#include <stdio.h>

#ifdef WIN32
#define llong __int64
#else
#define llong lon long
#endif

#define MOD 666013


int* mult(int* a, int *b)
{
	int* result = new int[4];
	for(int i=0;i<2;++i)
	{
		for(int j=0;j<2;++j)
		{
			result[i*2+j] = 0;
			for(int k=0;k<2;++k)
				result[i*2+j] += (((llong)a[i*2+k]) * b[k*2+j]) % MOD;
			result[i*2+j] %= MOD;
		}
	}

	return result;
}

int* put(int* a, int k)
{
	if(k == 1)
	{
		int* result = new int[4];
		for(int i=0;i<4;++i)
			result[i] = a[i];
		return result;
	}
	if( k%2 == 0 )
	{
		int* r = put(a, k/2);
		int* result = mult(r, r);
		delete[] r;
		return result;
	}

	int* r = put(a, k-1);
	int* result = mult(a, r);
	delete[] r;
	return result;
}

int main(void)
{
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	int k;
	scanf("%d", &k);
	int a[4] = {0,1,1,1};
	int* r = put(a, k-1);

	printf("%d\n", r[3] % MOD);

	delete[] r;

	return 0;
}