#include <fstream>
using namespace std;

long long r[3][3],a[3][3],aux[3][3];

ifstream in("kfib.in");
ofstream out("kfib.out");

void pow(long long c[3][3],long long a[3][3],long long b[3][3])
{
	for (int i=1;i<3;i++)
		for (int j=1;j<3;j++)
		{
			c[i][j]=0;
			for (int k=1;k<3;k++,c[i][j]%=666013)
				c[i][j]+=a[i][k]*b[k][j];
		}
}

void copy(long long a[3][3],long long b[3][3])
{
	for (int i=1;i<3;i++)
		for (int j=1;j<3;j++)
			a[i][j]=b[i][j];
}

int main()
{
	int n;
	in>>n;
	r[1][1]=0;
	r[1][2]=r[2][1]=r[2][2]=1;
	a[1][1]=a[2][2]=1;
	a[2][1]=a[1][2]=0;
	for (;n;n>>=1)
	{
		if (n&1)
		{
			pow(aux,a,r);
			copy(a,aux);
		}
		pow(aux,r,r);
		copy(r,aux);
	}
	out<<a[1][2]<<"\n";
	return 0;
}