#include <iostream>
#define MOD 666013

using namespace std;

typedef long long tipus;


tipus k;
tipus a[3][3];


void masol(tipus a[3][3],tipus b[3][3]){
	int i,j;
	
	for(i=1;i<=2;i++){
		for(j=1;j<=2;j++)
			b[i][j]=a[i][j];
		
	}
	
}


void szoroz(tipus a[3][3],tipus b[3][3]){
	
	int i,j,k;
	tipus c[3][3],d[3][3];
	
	masol(a,c);
	masol(b,d);
	

	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			a[i][j]=0;
	
		for(i=1;i<=2;i++)
			for(j=1;j<=2;j++)
				for(k=1;k<=2;k++)
					a[i][j]=(a[i][j]+(c[i][k]*d[k][j])%MOD)%MOD;
	
	
}



void expo(tipus k){
	
	if(k>1)
		if(k%2==0){
			
			expo(k/2);
			
			szoroz(a,a);
			
		}else{
			
			tipus b[3][3];
			
			masol(a,b);
			
			expo((k-1)/2);
			
			szoroz(a,a);
			szoroz(a,b);
			
		}
	
}


int main(){
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	a[1][1]=0;a[1][2]=1;
	a[2][1]=1;a[2][2]=1;
	
	scanf("%lld",&k);
	
	expo(k-1);
	
	printf("%lld",a[2][2]);
	
	return 0;}