#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;
}