#include <fstream>
#include <cstring>
 
std::ifstream cin("kfib.in");
std::ofstream cout("kfib.out");
 
int k, S[2][2], M[2][2];

void matrix_multiplication(int A[][2], int B[][2], int C[][2]) {
  for (int i {0}; i < 2; ++i)
    for (int j {0}; j < 2; ++j)
      for (int k {0}; k < 2; ++k)
        C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % 666013;
}

void solve(int k) {
  int AUX[2][2];
  
  S[0][0] = 0;
  S[1][1] = 1;
  
  for (int i {1}; i <= k; i <<= 1) {
    if (i & k) {
      memset(AUX, 0, sizeof(AUX));
      matrix_multiplication(M, S, AUX);
      memcpy(S, AUX, sizeof(M));
    }

    memset(AUX, 0, sizeof(AUX));
    matrix_multiplication(M, M, AUX);
    memcpy(M, AUX, sizeof(M));
  }
}

int main() {
  M[0][0] = 0;
  M[0][1] = M[1][0] = M[1][1] = 1;
  
  cin >> k;
  solve(k - 1);
  cout << S[1][1];
  
  cin.close();
  cout.close();
  return 0;
}