#include <cstdio>
#include <cstring>
#define REST 666013
typedef 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(long k, mat22 a) {
long exponent=k;
int lt=sizeof(mat22);
mat22 baza,rez,rez2;
//printf("%d\n",lt);
memcpy(baza,a,lt);
while(exponent>0) {
while(!(exponent%2)) {
inmultire(baza,baza,rez);
//scriere(rez);
memcpy(baza,rez,lt);
exponent>>=1;
}
exponent--;
inmultire(rezultat,baza,rez2);
memcpy(rezultat,rez2,lt);
}
//scriere(rezultat);
}
int main()
{
long k,i,j,f1,f2;
mat22 a,b;
FILE *f=fopen("kfib.in","r");
FILE *g=fopen("kfib.out","w");
fscanf(f,"%ld",&k);
putere(k-1,mi);
fprintf(g,"%ld",rezultat[0][0]);
fclose(f);
fclose(g);
return 0;
}