#include<cstdio>
#include<string.h>

#define MOD 666013
int m1[2][2],m2[2][2];
int n;
void mult(int a[][2],int b[][2], int c[][2])
{
	int i,j,k;
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			for(k=0;k<2;k++)
				c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;


}

void putere(int p, int m[][2])
{
	int a[2][2],aux[2][2],i;
	memcpy(a,m1,sizeof(m1));
    m[0][0] = m[1][1] = 1;
	for(i=0;(1<<i)<=p;i++)
	{
		if(p&(1<<i))
		{
			memset(aux,0,sizeof(aux));
			mult(m,a,aux);
			memcpy(m,aux,sizeof(aux));
		}
		memset(aux,0,sizeof(aux));
		mult(a,a,aux);
		memcpy(a,aux,sizeof(a));


	}


}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	m1[0][0]=0;
	m1[0][1]=1;
	m1[1][0]=1;
	m1[1][1]=1;
	putere(n-1,m2);
	printf("%d",m2[1][1]);

	return 0;
}