#include <bits/stdc++.h>
using namespace std;

const int mod = 666013;

array<int, 4> multiplyMatrix(const array<int, 4>& a, const array<int, 4>& b) {
  array<int, 4> x;
  x[0] = ((long long)a[0] * b[0] + (long long)a[1] * b[2]) % mod;
  x[1] = ((long long)a[0] * b[1] + (long long)a[1] * b[3]) % mod;
  x[2] = ((long long)a[2] * b[0] + (long long)a[3] * b[2]) % mod;
  x[3] = ((long long)a[2] * b[1] + (long long)a[3] * b[3]) % mod;
  return x;
}

void print(const array<int, 4>& x) {
  printf("%d %d\n%d %d\n\n", x[0], x[1], x[2], x[3]);
}

void solve() {
  array<int, 4> c {0, 1, 1, 1};
  array<int, 4> r {1, 0, 0, 1};
  
  int k;
  cin >> k;
  while (k) {
    if (k & 1) r = multiplyMatrix(r, c);
    c = multiplyMatrix(c, c);
    k >>= 1;
  }

  cout << r[2] << endl;
}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();
}