#include<fstream>
using namespace std;
#define m 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
int k;
long a[3][3],b[3][3],c[3][3],rez[3][3],ct[3][3];
void prod(long a[][3] , long b[][3])
{	long aux[3][3];
	aux[1][1]=aux[1][2]=aux[2][1]=aux[2][2]=0;
	int i,j,t;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			for(t=1;t<=2;t++)
				aux[i][j]=(aux[i][j]+1LL*a[i][t]*b[t][j])%m;
			
	for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) rez[i][j]=aux[i][j];
}
long pow(int k)
{	if(k==1)
		for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) rez[i][j]=ct[i][j];
	else
		if(k%2)
		{	pow(k-1);
			prod(ct,rez);
		}
		else
		{	pow(k/2);
			prod(rez,rez);
		}
}
int main()
{	f>>k;
	ct[1][1]=0; ct[1][2]=ct[2][1]=ct[2][2]=1;
	pow(k-1);
	g<<rez[2][2];
	f.close();
	g.close();
	return 0;
}