#include<stdio.h>
#include<string.h>
#define mod %666013
#define ll long long

int i,j;
long long k,n,p[3][3],a[3][3],x[3][3],c[3][3],ok=0;

void copy(ll a[3][3],ll c[3][3],ll n,ll m)
{
	int q,qq;
	
	for (q=1;q<=n;q++)
		for (qq=1;qq<=m;qq++)
			a[q][qq]=c[q][qq]mod;
}


void putere(ll a[3][3],ll b[3][3],ll n,ll m)
{
	int q,qq,qqq;
	memset(c,0,sizeof(c));
	
	for (q=1;q<=n;q++)
		for (qq=1;qq<=m;qq++)
			for (qqq=1;qqq<=n;qqq++)
				c[q][qq]=c[q][qq]+a[q][qqq]*b[qqq][qq];
			
	copy(a,c,n,m);
}


int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%lld",&k);
	k-=2;
	
	a[1][2]=1;a[2][1]=1;a[2][2]=1;
	
	while (k!=1)
		if (k%2==0)
		{
			k/=2;
			putere(a,a,2,2);
		}
		else
		{
			k--;
			if (ok==0)
			{
				ok=1;
				copy(p,a,2,2);
			}
			else putere(p,a,2,2);
		}
	putere(a,p,2,2);
		
	x[1][1]=1;
	x[2][1]=1;
	
	putere(a,x,2,1);

	printf("%lld\n",a[2][1] mod);
	
	return 0;
}