#include<stdio.h>
#include<string.h>
#define mod 666013
using namespace std;

long long A[4][4],Z[4][4],i,j,k,ok;
int n;

void rez(long long a[4][4],long long b[4][4])
{ long long c[4][4];int k;

memset(c,0,sizeof(c));

	for (i=0;i<2;++i)
		 for (j=0;j<2;++j)
			  for (k=0;k<2;++k)
				   c[i][j]=(1LL*c[i][j]+1LL*a[i][k]*b[k][j])%mod;
			  
	memcpy(A,c,sizeof(A));
}

int main()
{
	FILE *f=fopen("kfib.in","r"), *g=fopen("kfib.out","w");
	
fscanf(f,"%d",&n);

Z[0][0]=0; Z[0][1]=1; 
Z[1][0]=1; Z[1][1]=1;

memcpy(A,Z,sizeof(Z));
k=1; ok=1;
while(ok)
{
	if(k*k < n)
	{ k*=k;
		rez(A,A);
	}
	else if( k+1 < n) {k++; rez(A,Z);}
	else break;
}
fprintf(g,"%d\n",A[1][1]);

fclose(f);
fclose(g);

return 0;
}