#include<cstdio>
long long a[3][3],b[3][3],c[3][3];
int main()
{
	int rez,n,k;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d %d",&n);
              k=666013;
	n=n-2;
	if (n==1) printf("1");else
		if (n==2) printf("1");else {
	b[1][1]=0;b[1][2]=b[2][1]=b[2][2]=1;
	c[1][1]=c[2][2]=1;
	c[1][2]=c[2][1]=0;
	while (n) 
	{  
		if (n%2==0) {
		a[1][1]=(((b[1][1]*b[1][1])%k)+((b[1][2]*b[2][1])%k)%k);
		a[1][2]=(((b[1][1]*b[1][2])%k)+((b[1][2]*b[2][2])%k)%k);
		a[2][1]=(((b[2][1]*b[1][1])%k)+((b[2][2]*b[2][1])%k)%k);
		a[2][2]=(((b[2][1]*b[1][2])%k)+((b[2][2]*b[2][2])%k)%k);
		n/=2;
		b[1][1]=a[1][1]%k;b[1][2]=a[1][2]%k;
		b[2][1]=a[2][1]%k;b[2][2]=a[2][2]%k;
		}else 
		{
		n--;
		a[1][1]=(((c[1][1]*b[1][1])%k)+((c[1][2]*b[2][1])%k)%k);
		a[1][2]=(((c[1][1]*b[1][2])%k)+((c[1][2]*b[2][2])%k)%k);
		a[2][1]=(((c[2][1]*b[1][1])%k)+((c[2][2]*b[2][1])%k)%k);
		a[2][2]=(((c[2][1]*b[1][2])%k)+((c[2][2]*b[2][2])%k)%k);
		c[1][1]=a[1][1]%k;c[1][2]=a[1][2]%k;
		c[2][1]=a[2][1]%k;c[2][2]=a[2][2]%k;
		}
	}
	printf("%lld",(c[2][2]+c[1][2])%k);
		}
	return 0;
}