#include <fstream>

using namespace std;

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

const unsigned long long int mod = 666013;

unsigned long long int mat[2][2] = {{0, 1}, {1, 1}};


void mply(){
  unsigned long long int cpy[2][2];
  cpy[0][0] = mat[0][0];
  cpy[0][1] = mat[0][1];
  cpy[1][0] = mat[1][0];
  cpy[1][1] = mat[1][1];

  mat[0][0] = ((cpy[0][0] * cpy[0][0] % mod) + (cpy[0][1] * cpy[1][0] % mod)) % mod;
  mat[0][1] = ((cpy[0][0] * cpy[0][1] % mod) + (cpy[0][1] * cpy[1][1] % mod)) % mod;
  mat[1][0] = ((cpy[1][0] * cpy[0][0] % mod) + (cpy[1][1] * cpy[1][0] % mod)) % mod;
  mat[1][1] = ((cpy[1][0] * cpy[0][1] % mod) + (cpy[1][1] * cpy[1][1] % mod)) % mod;
}

int fib(int put){
  int b = put - 2;
  unsigned long long int ret[2][2] = {{0, 1}, {1, 1}};

  while (b){
    if (b & 1){
      unsigned long long int cpy[2][2];
      cpy[0][0] = ret[0][0];
      cpy[0][1] = ret[0][1];
      cpy[1][0] = ret[1][0];
      cpy[1][1] = ret[1][1];

      ret[0][0] = ((cpy[0][0] * mat[0][0] % mod) + (cpy[0][1] * mat[1][0] % mod)) % mod;
      ret[0][1] = ((cpy[0][0] * mat[0][1] % mod) + (cpy[0][1] * mat[1][1] % mod)) % mod;
      ret[1][0] = ((cpy[1][0] * mat[0][0] % mod) + (cpy[1][1] * mat[1][0] % mod)) % mod;
      ret[1][1] = ((cpy[1][0] * mat[0][1] % mod) + (cpy[1][1] * mat[1][1] % mod)) % mod;
    }

    b >>= 1;


    mply();
  }

  return ret[1][1];
}

int main(){
  unsigned long long int k;
  in >> k;

  if (k == 0)
    out << 0;
  if (k == 1)
    out << 1;
  if (k >= 2)
    out << fib(k);

  return 0;
}