using namespace std;
#include<fstream>
ifstream eu("kfib.in");
ofstream tu("kfib.out");
# define MOD 666013
# define ll long long
ll p;
ll Sol[3][3],A[3][3],Aux[3][3];
void mul(ll A[3][3],ll B[3][3],ll Aux[3][3])
{
	int i,j,k;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			long long sum=0;
			for(k=1;k<=2;k++)
				sum+=A[i][k]*B[k][j];
			Aux[i][j]=sum%MOD;
		}
}
void copy(ll A[3][3],ll B[3][3])
{
	int i,j;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			A[i][j]=B[i][j];
}
int main()
{
	int i,j;
	eu>>p;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			A[i][j]=1;
			A[1][1]=0;
			Sol[1][1]=Sol[2][2]=1;
		}
		p-=1;
	while (p)
	{
		if(p%2==1)
		{
			mul(Sol,A,Aux);
			copy(Sol,Aux);
		}
		mul(A,A,Aux);
		copy(A,Aux);
		p=p/2;
	}
	tu<<Sol[2][2];
	return 0;
}