#include <fstream>
#include <vector>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
#define MOD 666013
vector<vector<long long>> matrixMult(vector<vector<long long>>a, vector<vector<long long>>b){
  vector<vector<long long>>result={{0,0},{0,0}};
  if(!a.size()||!b.size()){
    return result;
  }
  for(unsigned int i=0;i<result.size();i++){
    for(unsigned int j=0;j<result[i].size();j++){
      long long nr = 0;
      for(unsigned int n=0;n<a.size();n++){
        nr = (nr + (a[i][n] * b[n][j])%MOD)%MOD;
      }
      result[i][j] = nr;
    }
  }
  return result;
}
vector<vector<long long>> logPow(vector<vector<long long>>z, int i){
  vector<vector<long long>>result={{1,0},{0,1}};
  while(i>0){
    if(i%2==1){
      result = matrixMult(result, z);
    }
    z = matrixMult(z,z);
    i/=2;
  }
  return result;
}
int main(){
  vector<vector<long long>>z={{0,1},{1,1}};
  int k;
  f>>k;
  vector<vector<long long>> r = logPow(z,k);
  g<<r[1][0];

  return 0;
}