#include<cstdio>
#define mod 666013
using namespace std;

long long x,y,z,n,i;

int main()
   {
       freopen("kfib.in","r",stdin);
       freopen("kfib.out","w",stdout);
       scanf("%d",&n);
	   n=n%(mod*2+2);
	   x=1;y=1;
	   for (i=3;i<=n;i++){
	    	z=(x+y)%mod;
	    	x=y;
	    	y=z;
	}
	if (n<=2) printf("1");
	else
	   printf("%d\n",y);
	return 0;
}