#include <stdio.h>
#define r 666013

void m_pow (long long*,long long);

int main () {
	FILE *in,*out;
	long long A[5]={0,1,1,1},n;
	in=fopen ("kfib.in","r"); out=fopen ("kfib.out","w");
	fscanf (in,"%lld",&n);
	m_pow (A,n);
	fprintf (out,"%lld\n",A[1]);
	fclose (in); fclose (out);
	return 0;
}

void m_pow (long long *a,long long n) {
	long long j[5]={1,0,0,1},k[5];
	k[0]=a[0]; k[1]=a[1]; k[2]=a[2]; k[3]=a[3];
	while (n) {
		if (n%2) {
			j[1]=(j[0]*k[1]+j[1]*k[3])%r;
			j[0]=(j[0]*k[0]+j[2]*k[2])%r;
			j[3]=(j[0]+j[1])%r;
			j[2]=j[1];
		}
		k[1]=(k[1]*(k[0]+k[3]))%r;
		k[0]=(k[0]*k[0]+k[2]*k[2])%r;
		k[3]=(k[0]+k[1])%r;
		k[2]=k[1];
		n/=2;
	}
	a[0]=j[0]; a[1]=j[1]; a[2]=j[2]; a[3]=j[3];
}