#include<stdio.h>
void produs(int a[3][3],int b[3][3])
{
	int aux[3][3],i,j,k;
	for(i=1 ; i<=2 ; ++i)
		for(k=1;k<=2;++k)
		{
			aux[i][k]=0;
			for(j=1;j<=2;++j)
				aux[i][k]=(aux[i][k]+(long long)a[i][j]*b[j][k]%666013)%666013;
		}
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
			a[i][j]=aux[i][j];
}
void putere(int a[3][3],int n)
{
	int i,j,p[3][3];
	p[1][1]=p[2][2]=1;
	p[2][1]=p[1][2]=0;
	while(n)
	{
		if(n%2)
			produs(p,a);
		produs(a,a);
		n/=2;
	}
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
			a[i][j]=p[i][j];
}
int main()
{
	int n,k,q[3][3];
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&k);
	q[1][1]=q[1][2]=q[2][1]=1;
	q[2][2]=0;
	putere(q,k);
	printf("%d",q[2][1]);
	return 0;
}