// Catalin Balan
// Wed Mar 31 15:56:37 EEST 2010
// Infoarena - al k-lea element al sirului fibonaci

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define CHUNK 8192
#define MOD 666013

#define FIN "kfib.in"
#define FOUT "kfib.out"

// inmulteste 2 matrici a,b rezultatul pune-l in c
void mult( int a[][2], int b[][2], int c[][2] )
{
	for (int i = 0; i <= 1; ++i)
		for (int j = 0; j <= 1; ++j)
		{
			c[i][j] = 0;
			for (int k = 0; k <= 1; ++k)
			{
				c[i][j] = ( c[i][j] + (long long) a[i][k] * b[k][j]) % MOD;
			}
		}
}

// ridica matricea a la puterea n
void ridica( int M[][2], int n)
{

	int e[2][2], aux[2][2];
	
	memcpy(e, M, sizeof(e));
	
	M[0][0] = M[1][1] = 1;
	M[0][1] = M[1][0] = 0;
	
	for (int i = 1; i <= n; i<<=1)
	{
		if (i&n)
		{
			memset(aux, 0, sizeof(aux));
			mult(M,e,aux);
			memcpy(M, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		mult(e,e,aux);
		memcpy(e, aux, sizeof(aux));

	}

}

int main(int argv, char ** argc)
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	int n;
	scanf("%d ", &n);

	int rez[2][2] = { {0,1}, {1,1} };


	ridica( rez, n-1 );
	
	printf("%d\n", rez[1][1]);
	
	return EXIT_SUCCESS;
}