#include <cstdio>
#include <algorithm>
#include <cassert>

void matrmult(int A[2][2], int B[2][2]){

  int aux[2][2];
  int i, j, k;

  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      aux[i][j]=0;
      for(k = 0; k < 2; k++)
	aux[i][j] = (aux[i][j] + ((((long long) A[i][k]) * B[k][j]) % 666013LL)) % 666013;
    }
  }

  memcpy(A, aux, sizeof aux);

}

void lgmult(int Z[2][2], int p){

  int R[2][2] = {{1, 0}, {0, 1}};
  int i;

  for(i = 0; (1<<i) <= p; i++){
    if(((1<<i) & p) > 0)
      matrmult(R, Z);

    matrmult(Z, Z);
  }

  memcpy(Z, R, sizeof R);

}

int main(){

  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);

  int fib;
  int Z[2][2] = {{0, 1}, {1, 1}};

  scanf("%d", &fib);

  lgmult(Z, fib-1);

  printf("%d\n", Z[1][1]);

  return 0;

}