/*
                        ( 0  1 )
( F(n - 2) F(n - 1) ) x (      ) = ( F(n - 1) F(n) )
                        ( 1  1 )
*/
#include <stdio.h>
#include <string.h>

#define MOD 666013

typedef int mat2[2][2];

mat2 ans = {{0, 1}}; // F[n - 1] = ans[0][0], F[n] = ans[0][1]

static inline void matrixMult(mat2 &A, mat2 &B, mat2 &C) {     // algoritm clasic de inmultire de matrice
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      C[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        C[i][j] = (C[i][j] + 1ULL * A[i][k] * B[k][j]) % MOD;     // (MOD - 1) ^ 2 ar cauza overflow, deci se face conversia in ULL
      }
    }
  }
  memcpy(A, C, sizeof(C));
}

void lgPut(int pow) {
  mat2 multiplyMat = {{0, 1}, {1, 1}};          // matricea cu care inmultesc
  mat2 tmp;

  for (; pow; pow >>= 1) {                      // algoritm clasic de ridicare la putere in timp logaritmic
    if (pow & 1) {
      matrixMult(ans, multiplyMat, tmp);
    }
    matrixMult(multiplyMat, multiplyMat, tmp);
  }
}

int main(void) {
  FILE *f = fopen("kfib.in", "r");
  int n;

  fscanf(f, "%d", &n);
  fclose(f);

  f = fopen("kfib.out", "w");

  if (!n) {
    fputc_unlocked('0', f);
  } else {
    lgPut(n - 1);
    fprintf(f, "%d\n", ans[0][1]);
  }
  fclose(f);
  return 0;
}