#include <fstream>

using namespace std;

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

int n, r[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 b) {
  int a[3][3];
  a[1][1] = 0; a[1][2] = 1;
  a[2][1] = 1; a[2][2] = 1;
  while (b) {
    if (b % 2 == 1)
      matmult (r, a);
    matmult (a, a);
    b /= 2;
  }
}

int main()
{
  fin >> n;
  r[1][1] = r[2][2] = 1;
  lg_put (n);
  fout << r[1][2];
  return 0;
}