#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const ll MOD=666013;
struct m2x2{
  ll a11,a12,a21,a22;
};
m2x2 Mi,Mr;
m2x2 modulo(m2x2 M){
    M.a11%=MOD;
    M.a12%=MOD;
    M.a21%=MOD;
    M.a22%=MOD;
    return M;
}
m2x2 inmultire(m2x2 M1, m2x2 M2){
  m2x2 R;
  R.a11=M1.a11*M2.a11+M1.a12*M2.a21;
  R.a12=M1.a11*M2.a12+M1.a12*M2.a22;
  R.a21=M1.a21*M2.a11+M1.a22*M2.a21;
  R.a22=M1.a21*M2.a12+M1.a22*M2.a22;
  return R;
}
m2x2 putere(m2x2 M, ll a){
  m2x2 REZ;
  REZ.a11=REZ.a22=1;
  REZ.a12=REZ.a21=0;
  while(a){
      if(a%2==1){
          REZ=inmultire(REZ,Mi);
          REZ=modulo(REZ);
      }
      Mi=inmultire(Mi,Mi);
      Mi=modulo(Mi);
      a/=2;
  }
  return REZ;
}
int main()
{
    ll k,rez;
    Mi.a11=0;
    Mi.a12=Mi.a21=Mi.a22=1;
    in>>k;
    Mr=putere(Mi,k-1);
    out<<Mr.a22;
    return 0;
}