#include <cstdio>
using namespace std;
long long a[2][2],b[2][2],c[2][2],n,con=666013;
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	a[0][0]=0;a[0][1]=1;
	a[1][0]=1;a[1][1]=1;
	b[0][0]=1;b[0][1]=0;
	b[1][0]=0;b[1][1]=1;
	scanf("%ld",&n);n--;
	while(n){
		if(n%2){
			c[0][0]=b[0][0]*a[0][0]+b[0][1]*a[1][0];
			c[0][1]=b[0][0]*a[0][1]+b[0][1]*a[1][1];
			c[1][0]=b[1][0]*a[0][0]+b[1][1]*a[1][0];
			c[1][1]=b[1][0]*a[0][1]+b[1][1]*a[1][1];
			b[0][0]=c[0][0]%con;
			b[0][1]=c[0][1]%con;
			b[1][0]=c[1][0]%con;
			b[1][1]=c[1][1]%con;
			   }
		c[0][0]=a[0][0]*a[0][0]+a[0][1]*a[1][0];
		c[0][1]=a[0][0]*a[0][1]+a[0][1]*a[1][1];
		c[1][0]=a[1][0]*a[0][0]+a[1][1]*a[1][0];
		c[1][1]=a[1][0]*a[0][1]+a[1][1]*a[1][1];
		a[0][0]=c[0][0]%con;
		a[0][1]=c[0][1]%con;
		a[1][0]=c[1][0]%con;
		a[1][1]=c[1][1]%con;
		n/=2;
		}
	printf("%lld",(b[0][0]+b[0][1])%con);
return 0;
}