#include <fstream>
#define MOD 666013
#define int long long

using namespace std;

ifstream cin ("kfib.in");
ofstream cout ("kfib.out");

struct matrice {
  int nmat, mmat, mat[2][2];
};

matrice mat1, mat2;

matrice inmultire_matrice(matrice A, matrice B) {
  int i, j, l;
  matrice matrice_rez;

  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++)
      matrice_rez.mat[i][j] = 0;

  for (i = 0; i < A.nmat; i++) /// parcurg linile matricei A
    for (j = 0; j < B.mmat; j++) /// parcurg coloanele matricei B
      for (l = 0; l < A.mmat; l++)
        matrice_rez.mat[i][j] = (matrice_rez.mat[i][j] + (A.mat[i][l] * B.mat[l][j]) % MOD) % MOD;

  matrice_rez.nmat = A.nmat;
  matrice_rez.mmat = B.mmat;

  return matrice_rez;
}

matrice rid_put(int n) {
  matrice matrice_rez;

  n -= 2;
  matrice_rez = inmultire_matrice(mat2, mat2);

  while (n > 0) {
    if (n % 2 == 1)
      matrice_rez = inmultire_matrice(matrice_rez, mat2);
    n /= 2;
    mat2 = inmultire_matrice(mat2, mat2);
  }

  return matrice_rez;
}

signed main() {
  int n;
  matrice sol;
  cin >> n;

  if (n == 0) {
    cout << 0;
    return 0;
  }
  else if (n == 1) {
    cout << 1;
    return 0;
  }
  else if (n == 2) {
    cout << 1;
    return 0;
  }

  mat1.nmat = 1;
  mat1.mmat = 2;
  mat1.mat[0][0] = 0; mat1.mat[0][1] = 1;

  mat2.nmat = 2;
  mat2.mmat = 2;
  mat2.mat[0][0] = 0; mat2.mat[0][1] = 1; mat2.mat[1][0] = 1; mat2.mat[1][1] = 1;

  sol = rid_put(n - 1);
  sol = inmultire_matrice(mat1, sol);

  cout << sol.mat[0][1];
  return 0;
}