#include <fstream>
#include <cstring>

using namespace std;

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

const int MOD = 666013;

int k;

int mat[3][3], sol[3][3], tmp[3][3], x[3][3];

void mult_mat(int a[][3], int b[][3], int c[][3]) {
  for(int i = 1; i <= 2; i++) {
    for(int j = 1; j <= 2; j++) {
      for(int k = 1; k <= 2; k++)
        c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
    }
  }
}

void lgput(int a[][3], int p) {
  memcpy(x, mat, sizeof(mat));
  a[1][1] = a[2][2] = 1;
  for(int i = 0; (1 << i) <= p; i++) {
    if((1 << i) & p) {
      memset(tmp, 0, sizeof(tmp));
      mult_mat(a, x, tmp);
      memcpy(a, tmp, sizeof(tmp));
    }
    memset(tmp, 0, sizeof(tmp));
    mult_mat(x, x, tmp);
    memcpy(x, tmp, sizeof(tmp));
  }
}

int main() {
  cin >> k;
  mat[1][1] = 0;
  mat[1][2] = mat[2][1] = mat[2][2] = 1;
  lgput(sol, k - 1);
  cout << sol[2][2];
  return 0;
}