#include <fstream>
#include <vector>

using namespace std;

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

const int MOD = 666013;

void mult1 (vector < int > m1, vector < vector < int > > m2, vector < int > &ans) {
   
  ans[0] = (1ll * m1[0] * m2[0][0] + 1ll * m1[1] * m2[1][0]) % MOD;
  ans[1] = (1ll * m1[0] * m2[0][1] + 1ll * m1[1] * m2[1][1]) % MOD;
}

void mult2 (vector < vector < int > > m1, vector < vector < int > > m2, vector < vector < int > > &ans) {
   
  ans[0][0] = (1ll * m1[0][0] * m2[0][0] + 1ll * m1[0][1] * m2[1][0]) % MOD;
  ans[0][1] = (1ll * m1[0][0] * m2[0][1] + 1ll * m1[0][1] * m2[1][1]) % MOD;
  ans[1][0] = (1ll * m1[1][0] * m2[0][0] + 1ll * m1[1][1] * m2[1][0]) % MOD;
  ans[1][1] = (1ll * m1[1][0] * m2[0][1] + 1ll * m1[1][1] * m2[1][1]) % MOD;
}

void Raise (vector < vector < int > > &m, int k) {

  vector < vector < int > > aux = m;
  while (k) {
    
    if (k & 1) {
      mult2 (m, aux, m);
    }

    mult2 (aux, aux, aux);
    k >>= 1;
  }
}

int main () {
  
  int k;
  cin >> k;

  if (k == 0) {
    cout << 0 << '\n';
    return 0;
  }

  vector < int > v {0, 1};
  vector < vector < int > > v2 {{0, 1}, {1, 1}};

  Raise (v2, k - 1);
  mult1 (v, v2, v);
  
  cout << v[0] << '\n';
}