#include<stdio.h>
const int N = 666013;
long long k;
long long a[3][3],b[3][3];
void inmultire_matrici(long long b[3][3],long long a[3][3])
{
	long long c[3][3];
	c[1][1]= ( (a[1][1]*b[1][1])%N + (a[1][2]*b[2][1])%N) %N;
	c[2][1]= ( (a[2][1]*b[1][1])%N + (a[2][2]*b[2][1])%N) %N;
	c[1][2]= ( (a[1][1]*b[1][2])%N + (a[1][2]*b[2][2])%N) %N;
	c[2][2]= ( (a[2][1]*b[1][2])%N + (a[2][2]*b[2][2])%N) %N;
	b[1][1]=c[1][1];
	b[1][2]=c[1][2];
	b[2][1]=c[2][1];
	b[2][2]=c[2][2];
}

void putere(long long k)
{
	if(k==1 || k==0)
		return;
	if(k%2==0)
	{
		putere(k/2);
		inmultire_matrici(b,b);
	}	
	else
	{
		putere( (k-1)/2 );
		inmultire_matrici(b,b);
		inmultire_matrici(b,a);
	}	
}

int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%lld",&k);
	if(k==0)
		printf("0\n");
	if(k==1)
		printf("1\n");
	a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
	b[1][1]=0;b[1][2]=1;b[2][1]=1;b[2][2]=1;
	putere(k);
	printf("%d\n",b[1][2]);
	return  0;
}