#include<bits/stdc++.h>
using namespace std;
const int N=2;
const int MOD=666013;
struct Matrix{
  vector<vector<int>> mat;
  int n,m;
  Matrix(int _n,int _m,int val){
    n=_n;
    m=_m;
    mat.resize(n,vector<int>(m,val));
  }
  Matrix (vector<vector<int>> x){
    mat=x;
    n=mat.size();
    m=mat[0].size();
  }
  Matrix mult(Matrix other){
    Matrix ans(n,other.m,0);
    if(m==other.n){
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          for(int k=0;k<other.m;k++){
            ans.mat[i][k]+=(1LL*mat[i][j]*other.mat[j][k])%MOD;
            ans.mat[i][k]%=MOD;
          }
        }
      }

      return ans;
    }
    else
      return ans;
  }
};
Matrix lgcput(Matrix b,int p){
  Matrix ans(b.n,b.m,0);
  ans.mat[0][0]=ans.mat[1][1]=1;
  while(p){
    if(p&1){
      ans=ans.mult(b);
    }
    b=b.mult(b);
    p/=2;
  }
  return ans;
}
int main()
{
  FILE*fin,*fout;
  fin=fopen("kfib.in","r");
  fout=fopen("kfib.out","w");
  int n;
  fscanf(fin,"%d",&n);
  Matrix f(2,2,0);
  f.mat[0][0]=f.mat[0][1]=f.mat[1][0]=1;
  f=lgcput(f,n-1);
  Matrix ans(2,1,0);
  ans.mat[0][0]=1;
  ans=f.mult(ans);
  fprintf(fout,"%d",ans.mat[0][0]);
  return 0;
}