#include <cstdio>
#include <cstring>

#define MOD 666013

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	int n;
	scanf ("%d",&n);

	if (n < 2) printf ("%d\n",n);
	
	long long v[4] = {0,1,1,1};
	long long rez[4] = {1,0,0,1};

	for(n = n-1;n;n>>=1)
	{
		long long tmp[4];

		if (n&1)
		{
			tmp[0] = rez[0]*v[0]+rez[1]*v[2];
			tmp[1] = rez[0]*v[1]+rez[1]*v[3];
			tmp[2] = rez[2]*v[0]+rez[3]*v[2];
			tmp[3] = rez[2]*v[1]+rez[3]*v[3];
			rez[0] = tmp[0]%MOD;
			rez[1] = tmp[1]%MOD;
			rez[2] = tmp[2]%MOD;
			rez[3] = tmp[3]%MOD;
		}

		tmp[0] = v[0]*v[0]+v[1]*v[2];
		tmp[1] = v[0]*v[1]+v[1]*v[3];
		tmp[2] = v[2]*v[0]+v[3]*v[2];
		tmp[3] = v[2]*v[1]+v[3]*v[3];
		v[0] = tmp[0]%MOD;
		v[1] = tmp[1]%MOD;
		v[2] = tmp[2]%MOD;
		v[3] = tmp[3]%MOD;
	}
	
	printf ("%lld\n",rez[3]);
	return 0;
}