#include <stdio.h>
long long t[4][4],a1[4][4],v[4][4],arr[4],arr2[4];
long long a,b,c,x,y,z,n;
void inm()
{
    for(int i=1;i<=2;i++)
     {
             for(int j=1;j<=2;j++)
             {
                     t[i][j]=0;
                     for(int k=1;k<=2;k++)
                     {
                             t[i][j]+=(int)v[i][k]*v[k][j]%666013;
                     }
             }
     }
     for(int i=1;i<=3;i++)
     {
             for(int j=1;j<=3;j++) v[i][j]=t[i][j];
     }
}
int rid(int putere)
{
     if(putere!=1)
     {
                  rid(putere/2);
                  inm();
                  if(putere%2==1)
                  {
                                 for(int i=1;i<=2;i++)
                                 {
                                         for(int j=1;j<=2;j++)
                                         {
                                                 t[i][j]=0;
                                                 for(int k=1;k<=2;k++)
                                                 {
                                                         t[i][j]+=(int)v[i][k]*a1[k][j]%666013;
                                                 }
                                         }
                                 }
                                 for(int i=1;i<=2;i++)
                                 {
                                         for(int j=1;j<=2;j++) v[i][j]=t[i][j];
                                 }
                  }
     }
}
int main()
{
    freopen ("kfib.in","r",stdin);
    freopen ("kfib.out","w",stdout);
    int k;
            scanf("%d",&k);
            a1[1][1]=0;
            a1[2][1]=1;
            a1[1][2]=1;
            a1[2][2]=1;
            for(int i=1;i<=2;i++)
            {
                    for(int j=1;j<=2;j++)
                    {
                            v[i][j]=a1[i][j];
                    }
            }
            arr[1]=0;
            arr[2]=1;
            rid(k-1);
            for(int i=1;i<=2;i++)
            {
                    for(int j=1;j<=2;j++)
                    {
                            arr2[i]+=arr[j]*t[j][i];
                            arr2[i]%=666013;
                    }
            }
            printf("%d\n",arr2[2]);
}