#include <fstream>

using namespace std;

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

int n, rf[3][3];
const int mod = 666013;

void copymat (int a[3][3], int b[3][3]) {
  for (int l = 1; l <= 2; l++)
    for (int c = 1; c <= 2; c++)
      a[l][c] = b[l][c];
}

void matmult (int a[3][3], int b[3][3]) {
  int mr[3][3] = {0};
  for (int l = 1; l <= 2; l++)
    for (int c = 1; c <= 2; c++)
      for (int k = 1; k <= 2; k++)
        mr[l][c] = (mr[l][c] + (1LL * a[l][k] * b[k][c]) % mod) % mod;
  copymat (a, mr);
}

void lg_put (int a[3][3], int b) {
  int r[3][3];
  r[1][1] = 1; r[1][2] = 0;
  r[2][1] = 0; r[2][2] = 1;
  while (b) {
    if (b % 2 == 1)
      matmult (r, a);
    matmult (a, a);
    b /= 2;
  }
  copymat (rf, r);
}

int main()
{
  int a[3][3];
  a[1][1] = 0; a[1][2] = 1;
  a[2][1] = 1; a[2][2] = 1;
  fin >> n;
  if (n == 0)
    fout << 0;
  else {
    lg_put (a, n - 1);
    fout << rf[2][2];
  }
  return 0;
}