# include <stdio.h>
int n,a,b,c,i;
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d\n",&n);
	n=n% (666013*2+2);
	a=1; b=1; 
	for (i=3; i<=n; i++)
	{
		c=(a+b)%666013;
		a=b;
		b=c;
	}
	printf("%d\n",b);
	return 0;
}