#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");

const long mod = 666013;
long long Z[3][3],Sol[3][3],aux[3][3],n,i,j;

int main()
{
  cin>>n;
  --n;
  Z[1][1]=0; Z[1][2]=1; Z[2][1]=1; Z[2][2]=1;
  for (i=1;i<=2;++i) 
     for (j=1;j<=2;++j) Sol[i][j]=Z[i][j];
  while(n){
          if (n%2){ 
                    for (i=1;i<=2;++i)
                       for (j=1;j<=2;++j) aux[i][j]=(Sol[i][1]*Z[1][j]+Sol[i][2]*Z[2][j])%mod;
                     for (i=1;i<=2;++i) 
                        for (j=1;j<=2;++j) Sol[i][j]=aux[i][j];
                     --n;
                    }
              else {
                    for (i=1;i<=2;++i)
                       for (j=1;j<=2;++j) aux[i][j]=(Z[i][1]*Z[1][j]+Z[i][2]*Z[2][j])%mod;
                    for (i=1;i<=2;++i)
                       for (j=1;j<=2;++j) Z[i][j]=aux[i][j];
                    n/=2;
                    }
           }
  cout<<Sol[2][1];   
return 0;
}