#include<stdio.h>
FILE *f,*g;
long long n,a,b,c,d,az,bz,cz,dz; long mod=666013;
void lgput(long long &a,long long &b,long long &c,long long &d,long long n)
{ if(n==1) { a=0; b=c=1; d=1; }
  else if(n%2==0) { lgput(a,b,c,d,n/2); az=((a*a)%mod+(b*c)%mod)%mod; bz=((a*b)%mod+(b*d)%mod)%mod; cz=((a*c)%mod+(c*d)%mod)%mod; dz=((c*b)%mod+(d*d)%mod)%mod; a=az; b=bz; c=cz; d=dz; }
  else { lgput(a,b,c,d,n/2); az=((a*b)%mod+(b*d)%mod)%mod; bz=((a*a)%mod+(b*c)%mod+(a*b)%mod+(b*d)%mod)%mod; cz=((c*b)%mod+(d*d)%mod)%mod; dz=((c*a)%mod+(c*d)%mod+(c*b)%mod+(d*d)%mod)%mod; a=az; b=bz; c=cz; d=dz; }
}
int main()
{ f=fopen("kfib.in","r"); g=fopen("kfib.out","w");
  fscanf(f,"%lld",&n);
  a=0; b=c=d=1; n--;
  lgput(a,b,c,d,n);
  fprintf(g,"%lld",d);
  fclose(g);
  return 0;
}