#include <cstdlib>
#include <cstdio>
#include <cstring>

int n,mod = 666013; 
int sol[3][3],z[3][3];

void copymat(int dest[][3],int source[][3])
{
     for ( int i = 0; i < 2 ; i++ )
         for ( int j = 0 ; j < 2 ; j++)
             dest[i][j] = source[i][j];
}
inline void mult (int dest[][3],int surs1[][3],int surs2[][3])
{
     for ( int k = 0; k < 2 ; k++ )
         for ( int i = 0; i < 2; i++ )
             for ( int  j = 0; j < 2 ; j++ )
                 dest[i][j] = (dest[i][j] + 1LL*surs1[i][k]*surs2[k][j] )%mod;
}

inline void ridputere( int mat[][3],int p )
{
     int aux[3][3],sol[3][3];
     
     sol[0][0] = sol[1][1] = 1;
     sol[1][0] = sol[0][1] = 0;
     while ( p )
     {
           if ( p%2 )
           {
                memset(aux,0,sizeof(aux));
                mult(aux,sol,mat);
                copymat(sol,aux);
                
                
           }
           memset(aux,0,sizeof(aux));
           mult(aux,mat,mat);
           copymat(mat,aux);
           p >>= 1;
           
     }
     copymat(mat,sol);
}
int main()
{
    FILE *f,*g;
    f = fopen("fib.in","r");
    g = fopen("fib.out","w");
    
    fscanf(f,"%d",&n); 
    fclose(f);
    
    z[0][0] = 0;
    z[0][1] = z[1][1] = z[1][0] = 1;
    
    ridputere(z,n-1);
   
    
    fprintf(g,"%d\n",z[1][1]);
    fclose(g);
    
    return 0;
}