#include <stdio.h>
#include <stdlib.h>

long long rez[5][5], rezc[5][5], i[5][5], ic[5][5];
int main(){
  FILE*fin=fopen("kfib.in", "r");
  FILE*fout=fopen("kfib.out", "w");
  int k;
  fscanf(fin, "%d", &k);
  rez[1][1]=rez[2][2]=1;
  i[1][2]=i[2][1]=i[2][2]=1;
  rezc[1][1]=rezc[2][2]=1;
  ic[1][2]=ic[2][1]=ic[2][2]=1;
  k-=2;
  while(k>0){
    if(k%2==1){
      rez[1][1]=rezc[1][1]*i[1][1]+rezc[1][2]*i[2][1];
      rez[1][2]=rezc[1][1]*i[1][2]+rezc[1][2]*i[2][2];
      rez[2][1]=rezc[2][1]*i[1][1]+rezc[2][2]*i[2][1];
      rez[2][2]=rezc[2][1]*i[1][2]+rezc[2][2]*i[2][2];
      k--;
    }
    else{
      k/=2;
      i[1][1]=ic[1][1]*ic[1][1]+ic[1][2]*i[2][1];
      i[1][2]=ic[1][1]*ic[2][1]+ic[1][2]*i[2][2];
      i[2][1]=ic[2][1]*ic[1][1]+ic[2][2]*i[2][1];
      i[2][2]=ic[2][1]*ic[2][1]+ic[2][2]*i[2][2];
    }
    rez[1][1]%=666013; rez[1][2]%=666013; rez[2][1]%=666013; rez[2][2]%=666013;
    i[1][1]%=666013; i[1][2]%=666013; i[2][1]%=666013; i[2][2]%=666013;
    rezc[1][1]=rez[1][1]; rezc[1][2]=rez[1][2]; rezc[2][1]=rez[2][1]; rezc[2][2]=rez[2][2];
    ic[1][1]=i[1][1]; ic[1][2]=i[1][2]; ic[2][1]=i[2][1]; ic[2][2]=i[2][2];
  }
//  printf("%d %d\n%d %d", rez[1][1], rez[1][2], rez[2][1], rez[2][2]);
  fprintf(fout, "%lld", rez[2][2]+rez[1][2]);
  return 0;
}