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

void multiply(long A[][2], long B[][2], long C[][2]) {
	int i,j,k;
	
	long X1[2][2], X2[2][2], R[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 n, long C[][2]) {

	if(n==1) return;
	
	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 k;
	
	scanf("%ld",&k);

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

	return 0;
}