#include <stdio.h>
#include <string.h>

#define modulo2 666013

void Multiplication(const int A[][2],const int B[][2],int C[][2])
{
	int aux[2][2] = {0};

	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			unsigned long long S=0;
			for(int k=0;k<2;k++) 
				S+=1LL*A[i][k]*B[k][j];
			aux[i][j]=1LL*S % modulo2;
		}
	memcpy(C,aux,sizeof(aux));
}

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

	int k, n, M[2][2], aux[2][2];

	M[0][0] = 0; M[0][1] = 1; M[1][0] = 1; M[1][1] = 1;
	aux[0][0] = 1; aux[0][1] = 0; aux[1][0] = 0; aux[1][1] = 1;
	scanf("%d", &k);

	n = k-1;	

	while(n!=1){
		if(n % 2==0){
			Multiplication(M,M,M);
			n/=2;
		} else {
			Multiplication(aux,M,aux);
			n--;
		}
	}
	Multiplication(M,aux,M);
	
	printf("%d", M[1][1]);

	return 0;
}