#include <stdio.h>
#define LMAX 3
#define MOD 666013
#define ll long long
int n,A[LMAX][LMAX],B[LMAX][LMAX],rez[LMAX][LMAX];
void mul(int A[LMAX][LMAX],int B[LMAX][LMAX])
{
	int i,j,k,aux[LMAX][LMAX];
	for (i=1; i<=2; i++)
		for (j=1; j<=2; j++)
		{
			aux[i][j]=0;
			for (k=1; k<=2; k++)
				aux[i][j]+=((ll)A[i][k]*B[k][j])%MOD;
			if (aux[i][j]>=MOD)
				aux[i][j]-=MOD;
		}
	for (i=1; i<=2; i++)
		for (j=1; j<=2; j++)
			A[i][j]=aux[i][j];
}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&n);
	rez[1][2]=1;
	B[1][1]=1; B[2][2]=1;
	A[1][2]=1; A[2][1]=1; A[2][2]=1; 
	while (n)
	{
		if (n & 1)
			mul(B,A);
		mul(A,A);
		n>>=1;
	}
	mul(rez,B);
	printf("%d\n",rez[1][1]);
	return 0;
}