#include<stdio.h>
const int r = 666013;
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]%r)%r;
		}
	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 p[3][3],i,j;
	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 qq[3][3],n;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	qq[1][1]=qq[1][2]=qq[2][1]=1;
	qq[2][2]=0;
	putere(qq,n);
	printf("%d",qq[2][1]);
	return 0;
}