#include<stdio.h>

long aux1[3][3],aux2[3][3];

void inmultire(long x[3][3], long y[3][3], long c[3][3])
{
	c[1][1]=(x[1][1]*y[1][1]+x[1][2]*y[2][1])%666013;
	c[1][2]=(x[1][1]*y[1][2]+x[1][2]*y[2][2])%666013;
}

void inmultire2(long x[3][3], long y[3][3], long c[3][3])
{
	c[1][1]=(x[1][1]*y[1][1]+x[1][2]*y[2][1])%666013;
	c[1][2]=(x[1][1]*y[1][2]+x[1][2]*y[2][2])%666013;
	c[2][1]=x[2][1]*y[1][1]+x[2][2]*y[2][1];
	c[2][2]=x[2][1]*y[1][2]+x[2][2]*y[2][2];
}

void putere(long z[3][3],long n,long rezultat[3][3])
{
	if(n==1) 
	{
		rezultat[1][1]=0;
		rezultat[1][2]=1;
		rezultat[2][1]=1;
		rezultat[2][2]=1;
	}
	else 
		{
			putere(z,n/2,aux1);
			inmultire2(aux1,aux1,aux2);
			if(n%2) inmultire2(z,aux2,rezultat);
			  else {
					  rezultat[1][1]=aux2[1][1]%666013;
					  rezultat[1][2]=aux2[1][2]%666013;
					  rezultat[2][1]=aux2[2][1]%666013;
					  rezultat[2][2]=aux2[2][2]%666013;
				   }
		}
	}
			
	
int main()
{
	long k;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%ld",&k);
	if(k==0) printf("0");
	   else if (k==1||k==2) printf("1"); 
				else 
					{
						long Mn[3][3],M1[3][3],Z[3][3],Zridicat[3][3];
						M1[1][1]=0;
						M1[1][2]=1;
						Z[1][1]=0;
						Z[1][2]=1;
						Z[2][1]=1;
						Z[2][2]=1;
						putere(Z,k-1,Zridicat);
						inmultire(M1,Zridicat,Mn);
						printf("%ld", (Mn[1][2]%666013 ) );
					}
	return 0;
}