#include <stdio.h> 

#define r 666013

int k;
long long a [5] [5], p [5] [5], c [5] [5];


void mul (long long a [] [5], long long b [] [5])
{
	c [1] [1]=(a [1] [1] * b [1] [1])%r;
	c [1] [1]+=(a [1] [2]*b [2] [1])%r;
	c [1] [1]%=r;
	c [1] [2]=(a [1] [1]*b [1] [2])%r;
	c [1] [2]+=(a [1] [2]*b [2] [2])%r;
	c [1] [2]%=r;
	c [2] [1]=(a [2] [1] * b [1] [1])%r;
	c [2] [1]+=(a [2] [2]*b [2] [1])%r;
	c [2] [1]%=r;
	c [2] [2]=(a [2] [1]*b [1] [2])%r;
	c [2] [2]+=(a [2] [2]*b [2] [2])%r;
	c [2] [2]%=r;
	a [1] [1]=c [1] [1];
	a [1] [2]=c [1] [2];
	a [2] [1]=c [2] [1];
	a [2] [2]=c [2] [2];
		
}

void plog ()
{
	for (; k; k >>= 1)
	{
	       if (k % 2)
		      mul (p, a); 
	       mul (a, a);
	}	       
}

int main ()
{
	freopen ("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	a [1] [1]=a [1] [2]=a [2] [1]=1;
	p [1] [1]=/*p [1] [2]=p [2] [1]=*/p [2] [2]=1;
	scanf ("%d", &k);
	if (k < 3)
	{
		if (k == 0)  printf("0\n"); 
		else	printf ("1\n");
		return 0;
	}	
	k-=2;
	plog ();
//	fprintf(stderr, "%lld %lld\n%lld %lld", p [1] [1], p [1] [2], p [2] [1], p [2] [2]); 
	printf ("%lld\n", (p [1] [1]+p[1] [2])%r);
	return 0;
}