#include<stdio.h>
#include<string.h>
#define M 666013
int n;
int a[2][2];
int rez[2][2];
inline void inmul(int a[2][2],int b[2][2])
{
	int c[2][2]={0};
	for(int i=0; i<2; ++i)
	{
		for(int j=0; j<2; ++j)
		{
			for(int k=0; k<2; ++k)
				c[i][j]=(int)(((long long)c[i][j]+(long long)a[i][k]*b[k][j])%M);
		}
	}
	memcpy(a,c,sizeof(c));
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	scanf("%d",&n);
	if(n<2)
	{
		printf("%d\n",n);
		return 0;
	}
	a[0][0]=a[0][1]=a[1][0]=1;
	rez[0][0]=rez[1][1]=1;

	--n;
	for(; n; n>>=1)
	{
		if(n&1)
			inmul(rez,a);
		inmul(a,a);
	}
	
	printf("%d\n",rez[0][0]);
	return 0;
}