#include <stdio.h>
#define modulo 666013

int main()
{
  long int m[][2] = {{1, 1}, {1, 0}};
  long int f[][2] = {{1, 0}, {0, 1}};
  long int p, i, k, a, b, c, d; 
  FILE *in = fopen("kfib.in", "r");
  FILE *out = fopen("kfib.out", "w");

  fscanf(in, "%ld", &k);

  for(p = k-1, i = 1; i <= p; i <<= 1)
  {  
    if(i & p)
    {
      a = ((f[0][0]*m[0][0]) % modulo + (f[0][1]*m[1][0]) % modulo) % modulo;
      b = ((f[0][0]*m[0][1]) % modulo + (f[0][1]*m[1][1]) % modulo) % modulo;
      c = ((f[1][0]*m[0][0]) % modulo + (f[1][1]*m[1][0]) % modulo) % modulo;
      d = ((f[1][0]*m[0][1]) % modulo + (f[1][1]*m[1][1]) % modulo) % modulo;

      f[0][0] = a; f[0][1] = b;
      f[1][0] = c; f[1][1] = d;
    }
    a = ((m[0][0]*m[0][0]) % modulo + (m[0][1]*m[1][0]) % modulo) % modulo;
    b = ((m[0][0]*m[0][1]) % modulo + (m[0][1]*m[1][1]) % modulo) % modulo;
    c = ((m[1][0]*m[0][0]) % modulo + (m[1][1]*m[1][0]) % modulo) % modulo;
    d = ((m[1][0]*m[0][1]) % modulo + (m[1][1]*m[1][1]) % modulo) % modulo;

    m[0][0] = a; m[0][1] = b;
    m[1][0] = c; m[1][1] = d;
  }

  if(i < 2)
    fprintf(out, "%ld\n", i);
  else
    fprintf(out, "%ld\n", f[0][0]);

  fclose(in);
  fclose(out);
  return 0;
}