#include <stdio.h>
#define modulo 666013
long int put, k, i, j;
typedef long long matrice[3][3];
matrice z, z1, aux;

void produs(matrice a, matrice b)
{
	aux[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%modulo;
	aux[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%modulo;
	aux[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%modulo;
	aux[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%modulo;
	for (i=1;i<=2;i++)
		for (j=1;j<=2;j++)
			z[i][j]=aux[i][j];
}

void putere(long int put)
{
	if (put==1)
	{	z[1][1]=0; z[1][2]=1; z[2][1]=1; z[2][2]=1;	}
	else
	{
		if (put%2==0)
		{
			putere(put/2);
			produs(z,z);
		}
		else
		{
			putere(put/2);
			produs(z,z);
			produs(z,z1);
		}
	}
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%ld",&k);
	z1[1][2]=1; z1[2][1]=1; z1[2][2]=1;
	if (k>2)
		putere(k-1);
	if (k==0)
		printf("0");
	else
		if (k<=2)
			printf("1");
		else
			printf("%ld",z[2][2]);
	return 0;
}