#include <stdio.h>
#define mod 666013
struct mat{int x11,x12,x21,x22;};

inline mat multiply(mat a, mat b){
  mat aux;
  aux.x11=(a.x11*b.x11+a.x12*b.x21)%mod;
  aux.x12=(a.x11*b.x12+a.x12*b.x22)%mod;
  aux.x21=(a.x21*b.x11+a.x22*b.x21)%mod;
  aux.x22=(a.x21*b.x12+a.x22*b.x22)%mod;
  return aux;
}
int main(){
  int p;
  mat a,r;
  freopen("kfib.in","r",stdin);
  freopen("kfib.out","w",stdout);
  scanf("%d",&p);
  r.x11=r.x22=1; r.x12=r.x21=0;
  a.x11=0; a.x12=a.x21=a.x22=1;
  while (p>0){
    if ((p&1)>0)r=multiply(r,a);
    a=multiply(a,a);
    p>>=1;
  }
  printf("%d\n",r.x12);
return 0;
}