#include<cstdio>
struct mat
{
	long long a[2][2];
	void operator*=(mat mt)
		{
			long long b[2][2],c[2][2];
			b[0][0]=mt.a[0][0];
			b[0][1]=mt.a[0][1];
			b[1][0]=mt.a[1][0];
			b[1][1]=mt.a[1][1];
			c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0];
			c[0][1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
			c[1][0]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
			c[1][1]=a[1][0]*b[0][1]+a[1][1]*b[1][1];
			a[0][0]=c[0][0]%666013;
			a[0][1]=c[0][1]%666013;
			a[1][0]=c[1][0]%666013;
			a[1][1]=c[1][1]%666013;
		}
}mm;
mat f (mat m,int e)
{
	if(e==1)
		return mm;
	mat r=f (m,e/2);
	r*=r;
	if(e%2)
		r*=mm;
	return r;
}
int main()
{
	freopen ("kfib.in","r",stdin);
	freopen ("kfib.out","w",stdout);
	int n;
	scanf ("%d",&n);
	if(n==0)
		puts ("0");
	else if(n==1)
		puts ("1");
	else{	
		mm.a[0][0]=mm.a[0][1]=mm.a[1][0]=1;
		mm.a[1][1]=0;
		printf ("%lld",f (mm,n-1).a[0][0]);
	}
}