#include<stdio.h>

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

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

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

void putere(long long z[3][3],long long n,long 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("%lld",&k);
	if(k==0) printf("0");
	   else if (k==1||k==2) printf("1"); 
				else 
					{
						long 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("%lld", (Mn[1][2] % 666013 ) );
					}
	return 0;
}