#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 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);
    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);
    }
    g<<(ans[0][1]+ans[1][1])%MOD;
    f.close ();
    g.close ();
    return 0;
}