#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
typedef struct
{
  int64_t **m;
  uint32_t rows,columns;
}matrix;
matrix *matrix_create(int64_t *values,uint32_t rows,uint32_t columns)
{
  matrix *aux=(matrix*)malloc(sizeof(matrix));
  aux->rows=rows;
  aux->columns=columns;
  int64_t **m=(int64_t**)malloc(rows*sizeof(int64_t*));
  for(uint32_t i=0;i<rows;i++)
    m[i]=(int64_t*)malloc(columns*sizeof(int64_t));
  for(uint32_t i=0;i<rows*columns;i++)
    m[i/columns][i%columns]=values[i];
  aux->m=m;
  return aux;
}
matrix *matrix_mult(matrix *a,matrix *b)
{
  if(a->columns!=b->rows)
    return NULL;
  int64_t *v=(int64_t*)calloc(a->rows*b->columns,sizeof(int64_t));
  matrix *ans=matrix_create(v,a->rows,b->columns);
  free(v);
  for(uint32_t i=0;i<a->rows;i++)
    for(uint32_t j=0;j<b->columns;j++)
      for(uint32_t k=0;k<a->columns;k++)
        ans->m[i][j]+=a->m[i][k]*b->m[k][j];
  return ans;
}
void matrix_delete(matrix *a)
{
  for(uint32_t i=0;i<a->rows;i++)
    free(a->m[i]);
  free(a->m);
  free(a);
}
void matrix_print(matrix *a)
{
  for(uint32_t i=0;i<a->rows;i++)
  {
    for(uint32_t j=0;j<a->columns;j++)
      printf("%ld ",a->m[i][j]);
    printf("\n");
  }
}
matrix *matrix_exponent(matrix *a,int pow)
{
  matrix *ans,*aux,*par,*impar;
  if(a->rows!=a->columns)
    return NULL;
  
  int64_t *v=(int64_t*)calloc(a->rows*a->columns,sizeof(int64_t));
  ans=matrix_create(v,a->rows,a->columns);
  free(v);
  
  if(pow==0)
  {
    for(uint32_t i=0;i<a->rows;i++)
      ans->m[i][i]=1;
    return ans;
  }
  
  aux=matrix_exponent(a,pow/2);
  par=matrix_mult(aux,aux);
  if(pow%2)
  {
    impar=matrix_mult(a,par);
    for(int i=0;i<a->rows;i++)
      for(int j=0;j<a->rows;j++)
	ans->m[i][j]=impar->m[i][j]%666013;
    matrix_delete(impar);
  }
  else
    for(int i=0;i<a->rows;i++)
      for(int j=0;j<a->rows;j++)
	ans->m[i][j]=par->m[i][j]%666013;

  matrix_delete(par);
  matrix_delete(aux);
  
  return ans;
}
int main()
{
  FILE *in=fopen("kfib.in","r"),*out=fopen("kfib.out","w");
  int64_t v1[]={0,1,1,1},v2[]={0,1};
  matrix *z=matrix_create(v1,2,2),*m1=matrix_create(v2,1,2);
  uint32_t k;
  fscanf(in,"%d",&k);
  if(k==0)
    fprintf(out,"%ld\n",m1->m[0][0]);
  else
  {
    matrix *exp=matrix_exponent(z,k-1);
    matrix *ans=matrix_mult(m1,exp);
    fprintf(out,"%ld\n",ans->m[0][1]);
    matrix_delete(exp);
    matrix_delete(ans);
  }
  matrix_delete(z);
  matrix_delete(m1);
  fclose(in);
  fclose(out);
  return 0;
}