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

#define REST 666013

void inmultire_matrice(int a[2][2], int b[2][2])
{
  long long aux_a[2][2], aux_b[2][2];
  
  aux_a[0][0] = a[0][0];
  aux_a[0][1] = a[0][1];
  aux_a[1][0] = a[1][0];
  aux_a[1][1] = a[1][1];

  aux_b[0][0] = b[0][0];
  aux_b[0][1] = b[0][1];
  aux_b[1][0] = b[1][0];
  aux_b[1][1] = b[1][1];

  a[0][0] = (aux_a[0][0] * aux_b[0][0] + aux_a[0][1] * aux_b[1][0]) % REST;
  a[0][1] = (aux_a[0][0] * aux_b[0][1] + aux_a[0][1] * aux_b[1][1]) % REST;
  a[1][0] = (aux_a[1][0] * aux_b[0][0] + aux_a[1][1] * aux_b[1][0]) % REST;
  a[1][1] = (aux_a[1][0] * aux_b[0][1] + aux_a[1][1] * aux_b[1][1]) % REST;
}

void putere(int k, int sol[2][2], int m[2][2])
{
  while(k > 0)
    {
      if(k % 2 == 1)
	{
	  inmultire_matrice(sol,m);
	}
      inmultire_matrice(m,m);
      k = k / 2;
    }
}

int main(void)

{
  int k, m[2][2], sol[2][2];
  FILE *fin;
  FILE *fout;

  m[0][0] = 1;
  m[0][1] = 1;
  m[1][0] = 1;
  m[1][1] = 0;

  sol[0][0] = 1;
  sol[0][1] = 0;
  sol[1][0] = 0;
  sol[1][1] = 1;
  
  if((fin = fopen("kfib.in","r"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }

  if((fout = fopen("kfib.out","w"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }

  fscanf(fin,"%d", &k);
  
  putere(k-1, sol, m);
  
  fprintf(fout,"%d\n",sol[0][1]);

  fclose(fin);
  fclose(fout);

  return 0;

}