#include<cstdio>
#define NM 4
#define MOD 666013
#define M 35
#define LL long long
LL a[2][2],b[M][2][2],c[2][2];
void copiez_a(LL a[2][2],LL b[M][2][2],LL num)
{
	int i,j,k;
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
		{
			b[num][i][j]=a[i][j];
			a[i][j]=0;
		}
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
			for (k=0; k<2; ++k)
			{
				a[i][j]+=(b[num][i][k]%MOD*b[num][k][j]%MOD)%MOD;
				if (a[i][j]>=MOD)
					a[i][j]-=MOD;
			}
}
void inmultesc(LL b[M][2][2],LL a[2][2],LL num)
{
	int i,j,k;
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
		{
			c[i][j]=0;
			for (k=0; k<2; ++k)
			{
				c[i][j]+=(a[i][k]%MOD*b[num][k][j]%MOD)%MOD;
				if (c[i][j]>=MOD)
					c[i][j]-=MOD;
			}
		}
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
			a[i][j]=c[i][j];
}
void putere(LL a[2][2],LL p,LL num)
{
	if (!p)
	{
		a[0][0]=a[1][1]=1;
		a[0][1]=a[1][0]=0;
		return;
	}
	if (p&1)
	{
		copiez_a(a,b,num);
		putere(a,p>>1,num+1);
		inmultesc(b,a,num);
	}
	else
	{
	copiez_a(a,b,num);
	putere(a,p>>1,num+1);
	}
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	int N;
	scanf("%d",&N);
	a[0][0]=0;
	a[0][1]=a[1][0]=a[1][1]=1;
	putere(a,N,0);
	printf("%d",a[0][1]);
	return 0;
}