/*
          ~Keep It Simple!~
*/

#define mod 666013

#include <stdio.h>

long long n,A[3][3],B[3][3];

void Multiply(long long a[3][3],long long b[3][3])
{
	int aux[3][3] = {0};
	  for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
			 for(int k=1;k<=2;k++)
				 aux[i][j]+= (a[i][k]*b[j][k])%mod;
	  for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
			  a[i][j] = aux[i][j];
}
void Pow(int k)
{
	while(k)
	{
		if(k%2)
		{
			Multiply(B,A);
			k--;
		}
		Multiply(A,A);
		k/=2;
	}

}
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);

    scanf("%lld",&n);
	A[1][1] = 0;
	A[1][2] = A[2][2] = A [2][1] = 1;
	B[1][1] = B[1][2] = B[2][1] = B[2][2] =1;
	Pow(n-2);
	printf("%lld",B[2][2]);
}