#include <fstream>
#define mod 666013
using namespace std;

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

unsigned long long k, a[3][3], m[3][3], aux[3][3], i, s, I, J, K;

int main()
{	f>>k;
	a[1][1]=0;
	a[1][2]=a[2][1]=a[2][2]=1;
	m[1][1]=m[2][2]=1;
	for (i=0; (1<<i)<=k-1; ++i)
	{	if ((1<<i)&(k-1))
		{	for (I=1; I<=2; ++I)
				for (J=1; J<=2; ++J)
				{	aux[I][J]=0;
					for (K=1; K<=2; ++K) aux[I][J]=(aux[I][J]+(m[I][K]*a[K][J])%mod)%mod;
				}
			for (I=1; I<=2; ++I)
				for (J=1; J<=2; ++J) m[I][J]=aux[I][J];
		}
		for (I=1; I<=2; ++I)
			for (J=1; J<=2; ++J)
			{	aux[I][J]=0;
				for (K=1; K<=2; ++K) aux[I][J]=(aux[I][J]+(a[I][K]*a[K][J])%mod)%mod;
			}
		for (I=1; I<=2; ++I)
			for (J=1; J<=2; ++J) a[I][J]=aux[I][J];
	}
	g<<m[2][2]<<'\n';
    return 0;
}