#include <stdio.h>

#define MOD 666013LL

void inmultire(long long a[2][2], long long b[2][2]){
  long long c[2][2] = {0};
  int i, j, k;
  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      for(k = 0; k < 2; k++){
	c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
      }
    }
  }

  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      a[i][j] = c[i][j];
    }
  }
}

void putere(long long a[2][2], int p){
  long long b[2][2] = {0};
  int i, j;
  b[0][0] = 1;
  b[1][1] = 1;
  while(p > 0){
    if(p % 2 == 1){
      inmultire(b, a);
    }
    inmultire(a, a);
    p/=2;
  }
  for(i = 0; i < 2; i++){
    for(j = 0; j < 2; j++){
      a[i][j] = b[i][j];
    }
  }
}

int main(void){
  FILE *fin = fopen("kfib.in", "r");
  FILE *fout = fopen("kfib.out", "w");
  int n;
  fscanf(fin, "%d", &n);
  long long a[2][2] = {{0, 1}, {1, 1}};
  if(n == 0){
    fprintf(fout, "0\n");
  }
  else{
    putere(a, n - 1);
    fprintf(fout, "%lld\n", a[1][1]);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}