#include<cstdio>
using namespace std;
long long a[2][2],F[2][2],n,a1[2][2],m=666013,k,p=1;
void inmulteste(long long a[2][2],long long b[2][2])
{
	long long r[2][2];
	r[0][0]=(a[0][0]*b[0][0])%m+(a[0][1]*b[1][0])%m;
	r[0][1]=(a[0][0]*b[0][1])%m+(a[0][1]*b[1][1])%m;
	r[1][0]=(a[1][0]*b[0][0])%m+(a[1][1]*b[1][0])%m;
	r[1][1]=(a[1][0]*b[0][1])%m+(a[1][1]*b[1][1])%m;
	a[0][0]=r[0][0]%m;
	a[0][1]=r[0][1]%m;
	a[1][0]=r[1][0]%m;
	a[1][1]=r[1][1]%m;
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%lld\n",&k);
	F[0][0]=1;
	F[0][1]=1;
	F[1][0]=1;
	F[1][1]=0;
	a1[0][0]=1;
	a1[0][1]=1;
	a1[1][0]=1;
	a1[1][1]=0;
	a[0][0]=1;
	a[0][1]=1;
	a[1][0]=1;
	a[1][1]=0;
	if(k==0) printf("0\n");
	if(k<=2) printf("1\n");
	else
	{
		n=k-2;
		while(n>1)
		{
			while(p<=n/2)
			{
				inmulteste(a1,a1);
				p=p*2;
			}
			n=n-p;
			inmulteste(a,a1);
			a1[0][0]=F[0][0];
			a1[0][1]=F[0][1];
			a1[1][0]=F[1][0];
			a1[1][1]=F[1][1];
			p=1;
		}
		if(n==1) inmulteste(a,F);
		printf("%lld\n",a[0][0]);
	}	
	fclose(stdin);
	fclose(stdout);
	return 0;
}