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

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

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

inline void ridputere( int mat[3][3],int p )
{
     int aux[3][3],sol[3][3],O[3][3];
     O[0][0] = O[0][1] = O[1][1] = O[1][0]= 0;
     sol[0][0] = sol[1][1] = 1;
     sol[1][0] = sol[0][1] = 0;
     while ( p )
     {
           if ( p%2 )
           {
                copymat(aux,O);
                mult(aux,sol,mat);
                copymat(sol,aux);
                
                
           }
           copymat(aux,O);
           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;
}