#include<stdio.h>

#define MOD 666013

typedef struct{
  long long a[2][2];
}Matrice;

Matrice multiply(Matrice A, Matrice B)
{
  Matrice C;

  C.a[0][0]=(A.a[0][0]*B.a[0][0] + A.a[0][1]*B.a[1][0])%MOD;
  C.a[0][1]=(A.a[0][0]*B.a[0][1] + A.a[0][1]*B.a[1][1])%MOD;
  C.a[1][0]=(A.a[1][0]*B.a[0][0] + A.a[1][1]*B.a[1][0])%MOD;
  C.a[1][1]=(A.a[1][0]*B.a[0][1] + A.a[1][1]*B.a[1][1])%MOD;

  return C;
}

Matrice putere(Matrice n,unsigned int p)
{
  Matrice r={{{1,0},{0,1}}};

  while(p>0)
    {
      if(p%2==1)
	r=multiply(r,n);
      n=multiply(n,n);
      p=p/2;
    }

  return r;
}

int main()
{
  FILE *fin=fopen("kfib.in","r");
  FILE *fout=fopen("kfib.out","w");

  if(fin==NULL || fout==NULL)
    {
      perror("eroare deschidere fisiere");
      return 1;
    }
    
  unsigned int k;

  if(fscanf(fin,"%u",&k)!=1)
    {
      printf("citire incorecta\n");
      return 1;
    }
  if(k==0)
    fprintf(fout,"0\n");
  else
    {
      Matrice Z={{{0,1},{1,1}}};

      Matrice r=putere(Z,k);
      fprintf(fout,"%lld\n",r.a[0][1]);
    }
  
  
  
  fclose(fin);
  fclose(fout);
  return 0;
}