#include<fstream>

using namespace std;

#define MOD 666013
#define ll long long

typedef ll matrice[2][2];

ifstream fi("kfib.in");
ofstream fo("kfib.out");

int k;
matrice zp,z={{0,1},{1,1}};

void prod(matrice &a, matrice &b, matrice &res) {
  res[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
  res[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
  res[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
  res[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
}

void copie(matrice &a, matrice &b) {
  a[0][0]=b[0][0];
  a[0][1]=b[0][1];
  a[1][0]=b[1][0];
  a[1][1]=b[1][1];
}

void putere(matrice &a, int p, matrice &res) {
  if(p==1) {
    copie(res,a);
    return;
  }
  matrice r;
  if(p%2) {
    putere(a,p-1,r);
    prod(a,r,res);
    return;
  }
  putere(a,p/2,r);
  prod(r,r,res);
}

int main() {
  fi>>k;
  fi.close();
  if(k<2) fo<<k<<"\n";
  else {
    putere(z,k-1,zp);
    fo<<zp[1][1]<<"\n";
  }
  fo.close();
  return 0;
}