#include <stdio.h>
long long k,m=666013;

void masol(long long a[3][3],long long b[3][3]){
b[1][1]=a[1][1];
b[1][2]=a[1][2];
b[2][1]=a[2][1];
b[2][2]=a[2][2];
}

void szoroz(long long c[3][3],long long b[3][3]){
long long b11=b[1][1],b12=b[1][2],b21=b[2][1],b22=b[2][2];
long long a[3][3];
masol(c,a);
b[1][1]=((a[1][1]*b11)%m+(a[1][2]*b21)%m)%m;
b[1][2]=((a[1][1]*b12)%m+(a[1][2]*b22)%m)%m;
b[2][1]=((a[2][1]*b11)%m+(a[2][2]*b21)%m)%m;
b[2][2]=((a[2][1]*b12)%m+(a[2][2]*b22)%m)%m;

}

void hatvany(long long a[3][3],long long k){

	if(k==1){
		}else{
			if(k%2==0){
			szoroz(a,a);
			hatvany(a,k/2);
			
		
			}else{
			long long c[3][3];
				masol(a,c);
				szoroz(a,a);
			hatvany(a,(k-1)/2);
			szoroz(c,a);
	
			}
		}
	
}


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

hatvany(a,k-1);

printf("%lld",a[2][2]);
return 0;
}