#include<fstream.h>
#define M 666013
#define Ai unsigned int
#define ALL unsigned long long
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef ALL mat[2][2];
mat Z,X;
Ai k;
void prodmat(mat A,mat B,mat C)
{int i,j,k;
 for(i=0;i<=1;i++)
	 for(j=0;j<=1;j++) 
	   {C[i][j]=0;
	    for(k=0;k<=1;k++) C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%M)%M;
	    }
}
void putere(mat A,mat B,Ai y)
{mat t,z;
 if(y==0) {B[0][0]=B[1][1]=1; B[1][0]=B[0][1]=0;}
       else if(y%2)  {putere(A,t,y/2); prodmat(t,t,z); prodmat(z,A,B);}
                else {putere(A,t,y/2); prodmat(t,t,B);}
}

int main()
{f>>k;
 if(k<2) g<<k<<"\n";
	   else  {Z[0][0]=0;Z[0][1]=Z[1][0]=Z[1][1]=1;
		      putere(Z,X,k-1); g<<X[1][1]<<"\n";
	          }
 g.close();
 return 0;
}