#include <cstdio>

int main()
{
	long long x11,x12,x21,x22,y11=0,y12=0,y21=0,y22=0,i,n;
	
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%lld",&n);
	x11=0;x12=x21=x22=1;n-=2;
	while (n)
	{
		if (n%2==1)
		{
			if (y11+y12+y21+y22!=0)
				{
					long long z11=y11,z12=y12,z22=y22,z21=y21;
					y11=(x11*z11+x12*z21)%666013;
					y12=(x11*z12+x12*z22)%666013;
					y21=(x21*z11+x22*z21)%666013;
					y22=(x21*z12+x22*z22)%666013;
			     } 
				    else
					
				y11=x11,y12=x12,y21=x21,y22=x22; 
		}
		long long  z11=x11,z12=x12,z22=x22,z21=x21;
					x11=(z11*z11+z12*z21)%666013;
					x12=(z11*z12+z12*z22)%666013;
					x21=(z21*z11+z22*z21)%666013;
					x22=(z21*z12+z22*z22)%666013;
		n/=2;
	}
    printf("%lld",(y21+y22)%666013);
	return 0;
}