#include <stdio.h>
#define modulo 666013
typedef  struct {
    long long x11,x12,x21,x22;
}matrix;

matrix inmultire(matrix a, matrix b){
  matrix aux;
  aux.x11=(a.x11*b.x11+a.x12*b.x21)%modulo;
  aux.x12=(a.x11*b.x12+a.x12*b.x22)%modulo;
  aux.x21=(a.x21*b.x11+a.x22*b.x21)%modulo;
  aux.x22=(a.x21*b.x12+a.x22*b.x22)%modulo;
  return aux;
}
int main(){
  int p;
  matrix a,Z;
  FILE *f=fopen("kfib.in","r");
 
  fscanf(f,"%d",&p);
  Z.x11=Z.x22=1; 
  Z.x12=Z.x21=0;
  a.x11=0; 
  a.x12=a.x21=a.x22=1;
  while (p>0){
    if ((p&1)>0)
        Z=inmultire(Z,a);
    a=inmultire(a,a);
    p>>=1;
  }
  f=fopen("kfib.out","w");
fprintf(f,"%lld\n",Z.x12);
return 0;
}