#include<cstdio>
#define MOD 666013
#define lld long long int
int k;
lld M[2][2] = {{0,1},{1,1}};
lld A[2][2] = {{1,0},{0,1}};
lld B[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",&k);
}
void solve()
{
	k--;
	while(k)
	{
		if(k&1)
		{
			//A = B*M
			B[0][0] = ((A[0][0]*M[0][0])%MOD+(A[0][1]*M[1][0])%MOD)%MOD;
			B[0][1] = ((A[0][0]*M[0][1])%MOD+(A[0][1]*M[1][1])%MOD)%MOD;
			B[1][0] = ((A[1][0]*M[0][0])%MOD+(A[1][1]*M[1][0])%MOD)%MOD;
			B[1][1] = ((A[1][0]*M[0][1])%MOD+(A[1][1]*M[1][1])%MOD)%MOD;
			A[0][0]=B[0][0];A[0][1]=B[0][1];A[1][0]=B[1][0];A[1][1]=B[1][1];
		}
		//M=M^2
		B[0][0] = ((M[0][0]*M[0][0])%MOD+(M[0][1]*M[1][0])%MOD)%MOD;
		B[0][1] = ((M[0][0]*M[0][1])%MOD+(M[0][1]*M[1][1])%MOD)%MOD;
		B[1][0] = ((M[1][0]*M[0][0])%MOD+(M[1][1]*M[1][0])%MOD)%MOD;
		B[1][1] = ((M[1][0]*M[0][1])%MOD+(M[1][1]*M[1][1])%MOD)%MOD;
		M[0][0]=B[0][0];M[0][1]=B[0][1];M[1][0]=B[1][0];M[1][1]=B[1][1];
		k>>=1;
	}
	printf("%lld\n",A[1][1]);
}