#include <stdio.h>
#include <stdlib.h>
int crez[3][3];
int rez[3][3];
int i[3][3];
int ci[3][3];
int main(){
  FILE *fin=fopen("kfib.in", "r"),*fout=fopen("kfib.out", "w");
  int n;
  fscanf(fin,"%d",&n);
  rez[1][1]=rez[0][0]=1;
  i[0][1]=i[1][0]=i[1][1]=1;
  n-=2;
  while(n!=0)
  {
    if(n%2==1)
    {
      crez[0][0]=rez[0][0];
      crez[0][1]=rez[0][1];
      crez[1][0]=rez[1][0];
      crez[1][1]=rez[1][1];
      rez[0][0]=(crez[0][0]*i[0][0])%666013+(crez[0][1]*i[1][0])%666013;
      rez[0][1]=(crez[0][0]*i[0][1])%666013+(crez[0][1]*i[1][1])%666013;
      rez[1][0]=(crez[1][0]*i[0][0])%666013+(crez[1][0]*i[1][0])%666013;
      rez[1][1]=(crez[1][0]*i[0][1])%666013+(crez[1][1]*i[1][1])%666013;
      n--;
    }
    else
    {
      ci[0][0]=i[0][0];
      ci[0][1]=i[0][1];
      ci[1][0]=i[1][0];
      ci[1][1]=i[1][1];
      i[0][0]=(ci[0][0]*i[0][0])%666013+(ci[0][1]*i[1][0])%666013;
      i[0][1]=(ci[0][0]*i[0][1])%666013+(ci[0][1]*i[1][1])%666013;
      i[1][0]=(ci[1][0]*i[0][0])%666013+(ci[1][0]*i[1][0])%666013;
      i[1][1]=(ci[1][0]*i[0][1])%666013+(ci[1][1]*i[1][1])%666013;
      n/=2;
    }
  }
  fprintf(fout,"%lld",(rez[0][1]+rez[1][1])%666013+1);
  return 0;
}