#include<cstdio>
using namespace std;

long long x,mod=666013, P[2][2]={1,0,0,1},B[2][2]={0,1,1,1},AUX[2][2];

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&x);
}

void solve()
{
	--x;
	while(x)
	{
		if(x&1)
		{
			AUX[0][0]=P[0][0]*B[0][0]%mod+P[0][1]*B[1][0]%mod;
			AUX[0][1]=P[0][0]*B[0][1]%mod+P[0][1]*B[1][1]%mod;
			AUX[1][0]=P[1][0]*B[0][0]%mod+P[1][1]*B[1][0]%mod;
			AUX[1][1]=P[1][0]*B[0][1]%mod+P[1][1]*B[1][1]%mod;
			P[0][0]=AUX[0][0];P[0][1]=AUX[0][1];P[1][0]=AUX[1][0];P[1][1]=AUX[1][1];
		}
		AUX[0][0]=B[0][0]*B[0][0]%mod+B[0][1]*B[1][0]%mod;
		AUX[0][1]=B[0][0]*B[0][1]%mod+B[0][1]*B[1][1]%mod;
		AUX[1][0]=B[1][0]*B[0][0]%mod+B[1][1]*B[1][0]%mod;
		AUX[1][1]=B[1][0]*B[0][1]%mod+B[1][1]*B[1][1]%mod;
		B[0][0]=AUX[0][0];B[0][1]=AUX[0][1];B[1][0]=AUX[1][0];B[1][1]=AUX[1][1];
		x>>=1;
	}
	printf("%lld\n",P[1][1]%mod);
}