#include<fstream.h>
#define M 666013
ifstream f("kfib.in"); 
ofstream g("kfib.out");
int T,k;
typedef long long mat[2][2];
mat A,U;
void prod(mat A, mat B, int n)
{mat C,D; int i,j,q; 
 if(n==0) {B[0][0]=B[1][1]=1; B[0][1]=B[1][0]=0;}   
 else    {prod(A,C,n/2);      
           if(n%2)      
	         {for(i=0; i<2; i++) for(j=0; j<2; j++)  
		        {D[i][j]=0; for(q=0; q<2; q++) D[i][j]+=C[i][q]*C[q][j]; D[i][j]%=M;}      
		      for(i=0; i<2; i++) for(j=0; j<2; j++)        
			     {B[i][j]=0; for(q=0; q<2; q++) B[i][j]+=D[i][q]*A[q][j]; B[i][j]%=M;}   
			 }     
           else        
             {for(i=0; i<2; i++) for(j=0; j<2; j++)        
	            {B[i][j]=0;
                 for(q=0; q<2; q++)
	                B[i][j]+=C[i][q]*C[q][j]; B[i][j]%=M;
				}     
	         }       
          }
}
int main()
{f>>k;
 if(k<2)
	g<<k<<'\n'; 
 else {A[0][0]=0; A[0][1]=A[1][1]=A[1][0]=1; 
		prod(A,U,k-2);  
		g<<(U[1][0]+U[1][1])%M;  
	}
g.close();
return 0;
}