#include <iostream>
#include <fstream>

using namespace std;

typedef unsigned long long ull;

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

int const MOD = 666013;
ull UNITY[3][3] = {{0, 0, 0}, {0, 1, 1}, {0, 1, 0}};

void multiply(ull a[3][3], ull b[3][3], ull ans[3][3]) {
  ull aux[3][3];
  aux[1][1] = a[1][1] * b[1][1] + a[1][2] * b[2][1];
  aux[1][2] = a[1][1] * b[1][2] + a[1][2] * b[2][2];
  aux[2][1] = a[2][1] * b[1][1] + a[2][2] * b[2][1];
  aux[2][2] = a[2][1] * b[1][2] + a[2][2] * b[2][2];

  ans[1][1] = aux[1][1] % MOD;
  ans[1][2] = aux[1][2] % MOD;
  ans[2][1] = aux[2][1] % MOD;
  ans[2][2] = aux[2][2] % MOD;
}

void computeFib(int n, ull fibm[3][3]) {
  ull fibAux[3][3];
  if(n == 1) {
    fibm[1][1] = 1;
    fibm[1][2] = 1;
    fibm[2][1] = 1;
    fibm[2][2] = 0;
    return;
  }
  fibAux[1][1] = 1;
  fibAux[1][2] = 1;
  fibAux[2][1] = 1;
  fibAux[2][2] = 0;
  while(n > 0){
    multiply(fibAux, fibAux, fibAux);
    if(n >> 1){
      multiply(fibAux, UNITY, fibAux);
    }
    n = n /2;
  }
}
//
int main() {
  int k;
  ull sol[3][3];
  in >> k;
  computeFib(k, sol);
  out << sol[1][2];
  return 0;
}