#include <cstdio>
#include <cstring>
#define REST 666013
typedef long long mat22[2][2];

mat22 mi={{1,1},{1,0}},rezultat={{1,0},{0,1}};
void scriere(mat22 a) {
	for(int i=0; i<2; i++) {
		for(int j=0; j<2; j++)
			printf("%ld ",a[i][j]);
		printf("\n");
	}
}

void inmultire(mat22 a,mat22 b, mat22 c) {
	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]=(c[i][j]+(a[i][k]*b[k][j]%REST))%REST;
		}
}

void putere(mat22 a, int exp) {
    mat22 baza,rez;
    memcpy(baza,a,sizeof(a));
    for(;exp;) {
        for(;0==exp%2;exp>>=1) {
            inmultire(baza,baza,rez);
            memcpy(baza,rez,sizeof(rez));
        }
        --exp;
        inmultire(baza,a,rez);
        memcpy(baza,rez,sizeof(rez));
    }
    memcpy(rezultat,baza,sizeof(baza));
}


int main()
{
	long long k,i,j,f1,f2;
	mat22 a,b;
	FILE *f=fopen("kfib.in","r");
	FILE *g=fopen("kfib.out","w");
	fscanf(f,"%lld",&k);
	putere(k-1,mi);
	fprintf(g,"%lld",rezultat[0][0]);
	fclose(f);
	fclose(g);
	return 0;
}