#include <stdio.h>
#include <string.h>
#define Nmax 3
#define LL long long
#define mod 666013

int M[3][3], mfin[3][3];
int n;

void mul(int a[][3],int b[][3],int c[][3]){
	int i,j,k;
	for(i=0; i<2; ++i)
		for(j=0; j<3; ++j)
			for(k=0; k<3; ++k) 
				c[i][j] =  (c[i][j] + (LL) a[i][k] * b[k][j]) % mod;
}

void ridic_la_putere(){
	int i;
	int aux[3][3];
	
	for(i=0; (1<<i)<=n; ++i){
		if( n & (1<<i) ){
			memset(aux,0,sizeof(aux));
			mul(mfin,M,aux);
			memcpy(mfin,aux,sizeof(aux));
		}
		
		memset(aux,0,sizeof(aux));
		mul(M,M,aux);
		memcpy(M,aux,sizeof(aux));
	}
}	

int main(){
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	
	M[0][0]=0; M[0][1]=1;
	M[1][0]=1; M[1][1]=1;
	
	mfin[0][0]=mfin[1][1]=1;
	
	n--;
	ridic_la_putere();
	
	printf("%d\n",mfin[1][1]);
	fclose(stdin); fclose(stdout);
	return 0;
}