#include <cstdio>
#include <cstring>
#define MOD 666013
int N;
int A[3][3],PU[3][3];

void calcp();
void inmulteste(int E[3][3],int F[3][3]);
void valori();


int main()
{

	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&N);
	
	A[1][1]=1;A[1][2]=1;A[2][1]=1;A[2][2]=0;
	
	calcp();
	
	printf("%d",PU[1][1]);
	
	return 0;
}

void calcp()
{
	while(N>1)
	{
		if(N%2)
			inmulteste(A,PU);
		inmulteste(A,A);
		N=N/2;
	}
}

void inmulteste(int E[3][3],int F[3][3])
{
	int T[3][3];
	T[1][1]=0,T[1][2]=0,T[2][1]=0,T[2][2]=0;

	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
		{
			for(int l=1;l<=2;l++)
				T[i][j]+=(E[i][l]*F[l][j])%MOD;
		}
	
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
				E[i][j]=T[i][j];
}