#include<stdio.h>
#define mod 666013
long long m[2][2], sol[2][2], temp[2][2], rez, n, i;

void atrib(long long a[2][2], long long b[2][2])
{	int i, j;
	for(i=0; i<2; i++)
		for(j=0; j<2; j++)
			a[i][j]=b[i][j];
}

void inm(long long a[2][2], long long b[2][2], long long c[2][2])
{	int i, j, k;
	for(i=0; i<2; i++)
		for(j=0; j<2; j++)
		{	c[i][j]=0;
			for(k=0; k<2; k++)
				c[i][j]=(((a[i][k]*b[k][j])%mod)+c[i][j])%mod;
		}	
}


int main()
{	
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%lld", &n);
	m[0][0]=0; m[0][1]=1;
	m[1][0]=1; m[1][1]=1;
	sol[0][0]=1; sol[1][1]=1;
	n--; n--;
	for(i=0; (1<<i)<=n; i++)
	{	if(((1<<i)&n)>0)
		{	inm(sol, m, temp);
			atrib(sol, temp);
		}
		inm(m, m, temp);
		atrib(m, temp);
	}
	
	rez=(sol[1][0]+sol[1][1])%mod;
	printf("%lld\n", rez);
	
	return 0;
	
}