#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mod 666013

void multiply(long long A[][2],long long B[][2],long long C[][2]) {
	int i,j,k;
	
	long long X1[2][2], X2[2][2];
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++) {
			X1[i][j]=A[i][j];
			X2[i][j]=B[i][j];
			C[i][j]=0;
		}
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			for(k=0;k<2;k++)
				C[i][j] = ( C[i][j] + (X1[i][k]*X2[k][j])%mod )%mod;
}

void expon(long long n,long long C[][2]) {

	if(n==1) return;
	
	long long D[2][2];
	
	if(n%2==0) {
		expon(n/2,C);
		multiply(C,C,C);
	}
	else {
		memcpy(D,C,sizeof(D));
		expon((n-1)/2,C);
		multiply(C,C,C);
		multiply(D,C,C);
	}
}

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

	long long C[2][2];
	
	C[0][0]=0;
	C[0][1]=C[1][0]=C[1][1]=1;	
	expon(k-1,C);
	
	printf("%lld",C[1][1]);

	return 0;
}