#include <iostream>
#include <fstream> 

using namespace std;

const int MOD = 666013;

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

void lgpow(long acc[2][2], long result[2][2], long exp) {
  long aux[2][2];
  
  int p = 0;
  // I = acc = (0, 1, 1, 1) ^ (2^p)
  // result = (0, 1, 1, 1) ^ (exp & ((2^p) - 1))
  while((1 << p) <= exp) {
    
    if(exp & (1 << p)) {
      memset(aux, 0, sizeof(aux));
      matrixMult(result, acc, aux);
      memcpy(result, aux, sizeof(aux));
    }

    p++;
    memset(aux, 0, sizeof(aux));
    matrixMult(acc, acc, aux);
    memcpy(acc, aux, sizeof(aux));
  }
}

int main() {
  ifstream in("kfib.in");
  ofstream out("kfib.out");
  
  int K;
  in >> K;
  long acc[2][2] = {{0, 1}, {1, 1}};
  long result[2][2] = {{1, 0}, {0, 1}};
  lgpow(acc, result, K - 1);
  out << result[1][1] << "\n";
  return 0;
}