#include <cstdio>

typedef long long i64;
typedef int mat[2][2];

const int MOD=666013;

void copy(mat A,mat B)
{
	int i,j;
	for (i=0;i<2;++i)
		for (j=0;j<2;++j)
			A[i][j]=B[i][j];
}

void mul(mat A,mat B)
{
	int i,j,k;
	mat C;
	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]=((i64)A[i][k]*B[k][j] + C[i][j])%MOD;
		}
	copy(A,C);
}

void pow(mat A,int n)
{
	mat R,C;
	int i,j;
	for (i=0;i<2;++i)
		for (j=0;j<2;++j) R[i][j]=0;
	for (i=0;i<2;++i) R[i][i]=1;
	copy(C,A);
	for (i=0;(1<<i)<=n;++i,mul(C,C))
		if ((1<<i)&n) mul(R,C);
	copy(A,R);
}

int main()
{
	int K;
	freopen("kfib.in","r",stdin);
	scanf("%d",&K);
	mat A;
	A[0][0]=0;A[0][1]=1;
	A[1][0]=1;A[1][1]=1;
	pow(A,K);
	freopen("kfib.out","w",stdout);
	printf("%d\n",A[0][1]);

	return 0;
}