#include <bits/stdc++.h>

using namespace std;

class rec {
private:
  int mod;
  int add(int a, int b) {
    a += b;
    if (a >= mod) {
      return a - mod;
    }
    if (a < 0) {
      return a + mod;
    }
    return a;
  }
  int mul(int a, int b) {
    return a * (long long) b % mod;
  }
  vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b) {
    vector<vector<int>> ans;
    int n = (int) b.size();
    if (n != (int) a[0].size()) {
      return ans;
    }
    for (int i = 0; i < (int) a.size(); i++) {
      ans.push_back({});
      for (int j = 0; j < n; j++) {
        ans[i].push_back(0);
        for (int k = 0; k < n; k++) {
          ans[i][j] = add(ans[i][j], mul(a[i][k], b[k][j]));
        }
      }
    }
    return ans;
  }
  vector<vector<int>> pw(vector<vector<int>> a, int b) {
    int n = (int) a.size();
    vector<vector<int>> r(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        r[i].push_back(0);
      }
      r[i][i] = 1;
    }
    while (b) {
      if (b & 1) {
        r = mul(r, a);
      }
      a = mul(a, a);
      b /= 2;
    }
    return r;
  }
  vector<vector<int>> init, mult;
public:
  void push(vector<int> coef, vector<int> term, int __mod) {
    mod = __mod;
    int n = (int) term.size();
    init.resize(1);
    init[0] = term;
    mult.resize(n);
    for (int i = 0; i < n; i++) {
      mult[i].resize(n, 0);
    }
    for (int i = 1; i < n; i++) {
      mult[i][i - 1] = 1;
    }
    for (int i = 0; i < n; i++) {
      mult[i][n - 1] = coef[i];
    }
  }
  int get(int t) {
    if (t < (int) init[0].size()) {
      return init[0][t];
    }
    return mul(init, pw(mult, t - 1))[0].back();
  }
} a;

int main() {
  freopen ("kfib.in", "r", stdin);
  freopen ("kfib.out", "w", stdout);
  a.push({1, 1}, {0, 1}, 666013);
  int t;
  cin >> t;
  cout << a.get(t) << "\n";
  return 0;
}