#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] + f[0][1]*m[1][0]) % modulo;
      b = (f[0][0]*m[0][1] + f[0][1]*m[1][1]) % modulo;
      c = (f[1][0]*m[0][0] + f[1][1]*m[1][0]) % modulo;
      d = (f[1][0]*m[0][1] + f[1][1]*m[1][1]) % modulo;

      f[0][0] = a; f[0][1] = b;
      f[1][0] = c; f[1][1] = d;
    }
    a = (m[0][0]*m[0][0] + m[0][1]*m[1][0]) % modulo;
    b = (m[0][0]*m[0][1] + m[0][1]*m[1][1]) % modulo;
    c = (m[1][0]*m[0][0] + m[1][1]*m[1][0]) % modulo;
    d = (m[1][0]*m[0][1] + m[1][1]*m[1][1]) % 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;
}