#include <stdio.h>

const long long MOD = 666013;

void lgput(long long MAT[][3], int p, long long sol[][3], FILE *fout) {
  long long a11, a22, a12, a21;
  sol[1][1] = 0;
  sol[1][2] = 1;
  sol[2][1] = 1;
  sol[2][2] = 1;
  while (p) {
    if ((p & 1) == 1) {
//      fprintf(fout, "%d %d\n%d %d\n\n", sol[1][1], sol[1][2], sol[2][1], sol[2][2]);
      a11 = sol[1][1];
      a12 = sol[1][2];
      a21 = sol[2][1];
      a22 = sol[2][2];
      sol[1][1] = (a11 * MAT[1][1] % MOD + a12 * MAT[2][1] % MOD) % MOD;
      sol[1][2] = (a11 * MAT[1][2] % MOD + a12 * MAT[2][2] % MOD) % MOD;
      sol[2][1] = (a21 * MAT[1][1] % MOD + a22 * MAT[2][1] % MOD) % MOD;
      sol[2][2] = (a21 * MAT[1][2] % MOD + a22 * MAT[2][2] % MOD) % MOD;
      p--;
//      fprintf(fout, "da\n%d %d\n%d %d\n\n", sol[1][1], sol[1][2], sol[2][1], sol[2][2]);
    }
    a11 = MAT[1][1];
    a12 = MAT[1][2];
    a21 = MAT[2][1];
    a22 = MAT[2][2];
    MAT[1][1] = (a11 * a11 % MOD + a12 * a21 % MOD) % MOD;
    MAT[1][2] = (a11 * a12 % MOD + a12 * a22 % MOD) % MOD;
    MAT[2][1] = (a21 * a11 % MOD + a22 * a21 % MOD) % MOD;
    MAT[2][2] = (a21 * a12 % MOD + a22 * a22 % MOD) % MOD;
    p /= 2;
  }
}

int main(){

  FILE *fin = fopen("kfib.in", "r");
  FILE *fout = fopen("kfib.out", "w");

  int N;
  long long x[3][3];
  int P;
  long long sol1[3][3];
  fscanf(fin, "%d", &N);

  if (N == 0) {
    fprintf(fout, "0\n");
    return 0;
  }

  if (N == 1) {
    fprintf(fout, "1\n");
    return 0;
  }

  x[1][1] = 0;
  x[1][2] = 1;
  x[2][1] = 1;
  x[2][2] = 1;

  lgput(x, N - 2, sol1, fout);

  fprintf(fout, "%d\n", sol1[2][2]);

  return 0;
}