#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

struct matrix {
  long long v[2][2];
  matrix () {
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        if (i != j) {
          v[i][j] = 0;
        }
        else {
          v[i][j] = 1;
        }
      }
    }
  }
  void operator = (const matrix& other) {
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        v[i][j] = other.v[i][j];
  }
  void operator += (const matrix& other) {
    matrix a;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        a.v[i][j] = v[i][j] + other.v[i][j];
        if (a.v[i][j] >= MOD) {
          a.v[i][j] -= MOD;
        }
      }
    }
    *this = a;
  }
  void operator *= (const matrix& other) {
    matrix a;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        a.v[i][j] = 0;
        for (int k = 0; k < 2; ++k) {
          a.v[i][j] += v[i][k] * other.v[k][j] % MOD;
          if (a.v[i][j] >= MOD) {
            a.v[i][j] -= MOD;
          }
        }
      }
    }
    *this = a;
  }
  void operator ^= (int exp) {
    matrix ans, cur;
    cur = *this;
    while (exp) {
      if (exp&1)
        ans *= cur;
      cur *= cur;
      exp /= 2;
    }
    *this = ans;
  }
};
matrix sol;
int main() {
  int n;
  freopen ("kfib.in", "r", stdin);
  freopen ("kfib.out", "w", stdout);
  scanf ("%d", &n);
  sol.v[0][0] = 0;
  sol.v[0][1] = 1;
  sol.v[1][0] = 1;
  sol.v[1][1] = 1;
  sol ^= n - 1;
  printf ("%d\n", sol.v[1][1]);
  return 0;
}