#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]) {
  int 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]) {
  if(n == 1) {
    fibm[1][1] = 1;
    fibm[1][2] = 1;
    fibm[2][1] = 1;
    fibm[2][2] = 0;
    return;
  }
  ull fibOld[3][3];
  computeFib(n/2, fibOld);
  multiply(fibOld, fibOld, fibm);
  if(n % 2 == 1) {  //n is odd ?
    multiply(fibm, UNITY, fibm);
  }
}

int main() {
  int k;
  ull sol[3][3];
  in >> k;
  computeFib(k, sol);
  out << sol[1][2];
  return 0;
}