#include <cstdio>
#define prim 666013
using namespace std;
FILE *f=fopen("kfib.in","r");
FILE *g=fopen("kfib.out","w");
long long a[2][2],b[2][2],k;
long long x[2][2],y[2][2],z[2][2];
int masca=1<<30,nr=30,put[35];
bool ok=false;


void produs()
{int i,j,t;
for (i=0;i<2;i++) for (j=0;j<2;j++)
            for (t=0;t<2;t++) z[i][j]+=1LL*x[i][t]*y[t][j];
for (i=0;i<2;i++) for (j=0;j<2;j++) {x[i][j]=z[i][j]%prim;
                                     y[i][j]=0;z[i][j]=0;}
}


int main()
{int i,j,t,p;
fscanf(f,"%d",&k);k--;
while (k!=0)
        {if ((masca&k)!=0)
                {k-=masca;
                 put[nr]=1;
                  }
         masca=masca>>1;
         nr--;
         }
a[0][1]=1;
a[1][0]=1;
a[1][1]=1;


for (p=0;p<=31;p++)
        {if (put[p]==1)
                {if (ok==false) {for (i=0;i<2;i++) for (j=0;j<2;j++) x[i][j]=a[i][j];
                                 ok=true;}
                           else {for (i=0;i<2;i++) for (j=0;j<2;j++) y[i][j]=a[i][j];
                                 produs();}
                 }
         for (i=0;i<2;i++) for (j=0;j<2;j++)
                    for (t=0;t<2;t++) b[i][j]+=1LL*a[i][t]*a[t][j];
         for (i=0;i<2;i++) for (j=0;j<2;j++) {a[i][j]=b[i][j]%prim;
                                              b[i][j]=0;}
         }
fprintf(g,"%d",x[1][1]);
return 0;
}