/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

const int INF = 2e9;
const int MOD = 666013;

class Matrix {
  public:
    vector <vector <int>> a;
    
    Matrix(int n, int m) {
      a.resize(1 + n);
      for(int i = 0; i <= n; i++)
        a[i].resize(1 + m);
    }
    
    void operator *= (const Matrix &aux) {
      assert(a[0].size() == aux.a.size());
      Matrix result(a[0].size() - 1, aux.a.size() - 1);

      for(int i = 1; i < a.size(); i++)
        for(int j = 1; j < aux.a[0].size(); j++)
          for(int k = 1; k < a[0].size(); k++)
            result.a[i][j] = (result.a[i][j] + 1LL * a[i][k] * aux.a[k][j]) % MOD;

      *this = result;
    }

    void Print() {
      for(int i = 1; i < a.size(); i++, cerr << '\n')
        for(int j = 1; j < a[i].size(); j++)
          cerr << a[i][j] << ' ';
    }
};

void FastPow(Matrix &A, int e) {
  Matrix result(2, 2);
  result.a[1][1] = result.a[2][2] = 1; // identity matrix

  while(e) {
    if(e & 1)
      result *= A;
    A *= A;
    e >>= 1;
  }

  A = result;
}

int main() {
  freopen("kfib.in", "r", stdin);
  freopen("kfib.out", "w", stdout);
  int n;
  scanf("%d", &n);

  Matrix A(2, 2), res(1, 2);
  A.a[1][2] = 1; A.a[2][1] = 1; A.a[2][2] = 1;
  res.a[1][2] = 1;

  FastPow(A, n - 1);

  res *= A;
  printf("%d\n", res.a[1][2]);
  return 0;
}