#include <stdio.h>
#include <string.h>
#define MODULO 666013

int A[2][2];
int n;


inline void mul(int A[][2], int B[][2], int C[][2]) 
{
	int i, j, k;
	for (i = 0; i < 2; i++)
		for (j = 0; j < 2; j++)
			for (k = 0; k < 2; k++) 
				C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MODULO;
			
}


inline void ridic(int A[][2], int put)
{
	A[0][0] = 0; A[1][0] = A[1][1] = A[0][1] = 1;
	if (put==1) return;
	
	int Aux[2][2], C[2][2];
	memset(Aux, 0, sizeof(Aux));
	memset(C, 0, sizeof(C));
	ridic(Aux, put/2);

	mul(Aux, Aux, C);
	memcpy(Aux, C, sizeof(Aux));
	if (put&1 == 1){
		memset(C, 0, sizeof(C));
		mul(A, Aux, C);
		memcpy(A, C, sizeof(C));
	}
	else
		memcpy(A, Aux, sizeof(Aux));
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);

	ridic(A, n-1);

	printf("%d\n",A[1][1]);
	return 0;
}