#include<stdio.h>
#define mod 666013

long long a[3][3],b,s[3][3],c[3][3],i,j,k,n;

void copiaza(long long a[3][3], long long b[3][3])
{
	a[1][1]=b[1][1];
	a[1][2]=b[1][2];
	a[2][1]=b[2][1];
	a[2][2]=b[2][2];
}


void inmulteste(long long a[3][3], long long b[3][3])
{
	c[1][1] = ( (a[1][1]*b[1][1]) % mod + (a[1][2]*b[2][1])% mod ) % mod;
	c[1][2] = ( (a[1][1]*b[1][2]) % mod + (a[1][2]*b[2][2])% mod ) % mod;
	c[2][1] = ( (a[2][1]*b[1][1]) % mod + (a[2][2]*b[2][1])% mod ) % mod;
	c[2][2] = ( (a[2][1]*b[1][2]) % mod + (a[2][2]*b[2][2])% mod ) % mod;
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	scanf("%d",&n);
	
	if(n==0) {printf("0"); return 0;}
		
	b=n-1;
	
	a[1][2]=a[2][1]=a[2][2]=1;
	s[1][1]=s[2][2]=1;
	
	while(b)
	{
		if(b&1) 
		{
			inmulteste(s,a);
			copiaza(s,c);
		}
		inmulteste(a,a);
		copiaza(a,c);
		
		b>>=1;
	}
	
	printf("%d",s[2][2]);
	return 0;
}