#include <cstdio>
#include <cstring>
#define MOD 666013

long long N;
long long PU[2][3];
long long A[3][3];

void calcp();
void inmulteste();
void inmulteste2();


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;
	PU[1][1]=1;
	
	calcp();
	
	printf("%d",PU[1][1]);
	
	return 0;
}

void calcp()
{
	N--;
	while(N)
	{
		if(N%2)
			inmulteste();
		inmulteste2();
		N=N/2;;
	}
}

void inmulteste()
{
	long long T[2][3];
	T[1][1]=0,T[1][2]=0;

	T[1][1]=(PU[1][1]*A[1][1]+PU[1][2]*A[2][1])%MOD;
	T[1][2]=(PU[1][1]*A[1][2]+PU[1][2]*A[2][2])%MOD;
	
	PU[1][1]=T[1][1]%MOD;
	PU[1][2]=T[1][2]%MOD;
}

void inmulteste2()
{
	long long T[3][3];
	
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			T[i][j]=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]=(T[i][j]+A[i][l]*A[l][j])%MOD;

	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			A[i][j]=T[i][j]%MOD;
	
}