#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;
typedef long long ll;

ll k;
ll z[][2]={{0,1},{1,1}};
ll za[2][2],ans[2][2];
void egaleaza(ll m[2][2],ll m2[2][2]){
  for(ll i=0;i<2;i++) for(ll j=0;j<2;j++)
    m[i][j]=m2[i][j];
}
void afis(ll m[2][2]){
  cout<<m[0][0]<<" "<<m[1][0]<<'\n'<<m[0][1]<<" "<<m[1][1]<<'\n';
  cout<<m[0][0]+m[1][0]<<" "<<m[0][1]+m[1][1]<<"\n\n";
}
void inmulteste(ll m[2][2],ll m2[2][2]){
    ll m3[2][2];
    egaleaza(m3,m);
    m[0][0]=(m2[0][0]*m3[0][0]+m2[0][1]*m3[1][0])%MOD;
    m[0][1]=(m2[0][0]*m3[0][1]+m2[0][1]*m3[1][1])%MOD;
    m[1][0]=(m2[1][0]*m3[0][0]+m2[1][1]*m3[1][0])%MOD;
    m[1][1]=(m2[1][0]*m3[0][1]+m2[1][1]*m3[1][1])%MOD;
}
void rp(ll m[2][2]){
  ll m2[2][2];
  egaleaza(m2,m);
  m[0][0]=(m2[0][0]*m2[0][0]+m2[0][1]*m2[1][0])%MOD;
  m[0][1]=(m2[0][0]*m2[0][1]+m2[0][1]*m2[1][1])%MOD;
  m[1][0]=(m2[1][0]*m2[0][0]+m2[1][1]*m2[1][0])%MOD;
  m[1][1]=(m2[1][0]*m2[0][1]+m2[1][1]*m2[1][1])%MOD;
}

int main()
{
    ifstream f ("kfib.in");
    ofstream g ("kfib.out");
    f>>k;k-=3;
    egaleaza(za,z);
    //afis(za);
    ans[0][0]=ans[0][1]=ans[1][0]=ans[1][1]=1;
    for(ll nr=1;nr<=k;nr<<=1){
      if((k|nr)==k)
        inmulteste(ans,za);
      rp(za);
      //afis(za);
    }
    g<<ans[0][1]+ans[1][1];
    f.close ();
    g.close ();
    return 0;
}