#include<cstdio>
#define m 666013
using namespace std;
int main()
{
	int i,n,f1,f2,f3;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	n=n%(m*2);
	f1=1,f2=1;
	for(i=3;i<=n;i++)
	f3=(f1+f2)%m,f1=f2,f2=f3;
	printf("%d\n",f3);
	return 0;
}