#include<cstdio>

const int Ky=666013;

int n,v[2][2],a[2][2];

void baz( int b[2][2],int c[2][2] )
{
	int aux[2][2];
	for( int i=0 ; i<2 ; ++i )
		for( int k=0 ; k<2 ; ++k )
			aux[i][k]= (b[i][0]*c[0][k]+b[i][1]*c[1][k])%Ky;
	for( int i=0 ; i<2 ; ++i )
		for( int j=0 ; j<2 ; ++j )
			b[i][j]=aux[i][j];
}

void rid( int n )
{
	if(n==0)
	{
		v[0][0]=v[1][1]=1;
		v[1][0]=v[0][1]=0;
	}
	rid(n/2);
	if(n%2==1)
		baz(v,a);
	baz(a,a);
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	a[0][0]=a[0][1]=a[1][0]=1;
	rid(n-1);
	printf("%d",(v[0][0]+v[0][1])%Ky);
	return 0;
}