#include<cstdio>
#include<cstring>
#define MOD 666013
#define ll long long
int k;
ll kfib;
int fibo[3][3] ,fib[3][3];
void inmultire_mat(int a[][3],int b[][3],int c[][3])
{
	for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)
					for(int k=0;k<2;++k)
						c[i][j] = ( c[i][j] + 1ll*a[i][k] * b[k][j] )%MOD;

}
void mat_kfib(int p , int m[][3])
{
	int c[3][3] , aux[3][3];
	memcpy(c,fib,sizeof(fib) );
	m[0][0]=m[1][1]=1;

	for(int i=0; (1<<i) <=p ; ++i)
	{
		if(p & (1<<i))
		{
			memset(aux,0,sizeof(aux));
			inmultire_mat(c,m,aux);
			memcpy(m,aux,sizeof(c));

		}

		memset(aux,0,sizeof(aux));
		inmultire_mat(c,c,aux);
		memcpy(c,aux,sizeof(c));
	}


}
int main ()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);

	scanf("%d",&k);
	fib[0][0]=0;
	fib[1][1]=fib[0][1]=fib[1][0]=1;
	
	mat_kfib(k-1,fibo);
	printf("%d\n",fibo[1][1]);
	return 0;

}