#include<cstdio>
long long rez[3][3],i[3][3],ci[3][3],crez[3][3];
int main()
{
 int k,j;
 freopen("kfib.in","r",stdin);
 freopen("kfib.out","w",stdout);
 scanf("%d",&k);
 rez[1][1]=rez[2][2]=1;
 i[1][2]=i[2][1]=i[2][2]=1;
 k-=2;
 while(k!=0)
      {
       if(k%2==1)
          {
           for(j=1;j<=2;j++)
              {
               crez[j][1]=rez[j][1];
               crez[j][2]=rez[j][2];
              }
           rez[1][1]=(crez[1][1]*i[1][1]+crez[1][2]*i[2][1])%666013;
           rez[1][2]=(crez[1][1]*i[1][2]+crez[1][2]*i[2][2])%666013;
           rez[2][1]=(crez[2][1]*i[1][1]+crez[2][2]*i[2][1])%666013;
           rez[2][2]=(crez[2][1]*i[1][2]+crez[2][2]*i[2][2])%666013;
           k--;
          }
       else
          {
           k/=2;
           for(j=1;j<=2;j++)
              {
               ci[j][1]=i[j][1];
               ci[j][2]=i[j][2];
              }
           i[1][1]=(ci[1][1]*ci[1][1]+ci[1][2]*ci[2][1])%666013;
           i[1][2]=(ci[1][1]*ci[2][1]+ci[1][2]*ci[2][2])%666013;
           i[2][1]=(ci[2][1]*ci[1][1]+ci[2][2]*ci[2][1])%666013;
           i[2][2]=(ci[2][1]*ci[2][1]+ci[2][2]*ci[2][2])%666013;
          }
      }
 printf("%lld\n",(rez[2][2]+rez[1][2])%666013);
return 0;
}