#include <cstdio>

struct Matrice {
  int n, m;
  int matr[2][2];
  void prod(Matrice a, Matrice b, int p) {
    int l, c, i, col;
    n = a.n;
    m = b.m;
    col = a.m;
    for(l = 0; l < n; l++)
      for(c = 0; c < m; c++) {
        matr[l][c] = 0;
        for(i = 0; i < col; i++) {
          matr[l][c] += a.matr[l][i] * b.matr[i][c];
          matr[l][c] %= p;
        }
      }
  }
};

Matrice prod(Matrice a, Matrice b, int p) {
  int l, c, i, col;
  Matrice x;
  x.n = a.n;
  x.m = b.m;
  col = a.m;
  for(l = 0; l < x.n; l++)
    for(c = 0; c < x.m; c++) {
      x.matr[l][c] = 0;
      for(i = 0; i < col; i++) {
        x.matr[l][c] += a.matr[l][i] * b.matr[i][c];
        x.matr[l][c] %= p;
      }
    }
  return x;
}

Matrice putere(Matrice baza, int exp, Matrice acum, int p) {
  if(exp == 0)
    return acum;
  else if(exp % 2 == 0)
    return putere(prod(baza, baza, p), exp / 2, acum, p);
  else
    return putere(prod(baza, baza, p), exp / 2, prod(acum, baza, p), p);
}

int main() {
  int n;
  Matrice a, b, c;
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  scanf("%d", &n);
  b.n = a.m = b.m = 2;
  a.n = 1;
  a.matr[0][0] = 0;
  a.matr[0][1] = 1;
  b.matr[0][0] = 0;
  b.matr[0][1] = 1;
  b.matr[1][0] = 1;
  b.matr[1][1] = 1;
  c = putere(b, n - 1, a, 10000);
  printf("%d", c.matr[0][1]);
  return 0;
}