#include <cstdio>
#include <cstdlib>
FILE*f=fopen("kfib.in","r");
FILE*g=fopen("kfib.out","w");
int a[2][2],y[2][2];

void inmult_matrici1(int e[2][2], int r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
     int c[2][2];
     int i,j,k;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             c[i][j]=0;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             for (k=1;k<=2;k++)
                 c[i][j]=(e[i][k]*r[k][j]+c[i][j])%666013;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             y[i][j]=c[i][j];
}
void inmult_matrici2(int e[2][2], int r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
     int c[2][2];
     int i,j,k;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             c[i][j]=0;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             for (k=1;k<=2;k++)
                 c[i][j]=(e[i][k]*r[k][j]+c[i][j])%666013;
     for (i=1;i<=2;i++)
         for (j=1;j<=2;j++)
             a[i][j]=c[i][j];
}
int main()
{
    int i,j,k;
    fscanf(f,"%d",&k);
    if (k==1) fprintf (g,"1");
    else
    {a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
    y[1][1]=1;y[1][2]=0;y[2][1]=0;y[2][2]=1;
    for (i=0;(1<<i)<=k-1;++i)
    {
        if (((1<<i)&k-1)>0)
           inmult_matrici1(y,a);
        inmult_matrici2(a,a);}
    
    fprintf(g,"%d",y[2][2]);}
    return 0;
}