#include <stdio.h>
#include <string.h>
#define mod 666013
FILE *f=fopen ("kfib.in", "r");
FILE *g=fopen ("kfib.out", "w");
long long A[3][3],B[3][3],S[3][3];
int v[1000],i,j,k;

void inmultire (long long A[3][3], long long B[3][3], long long C[3][3]) {
int i,j,k;
memset(S, 0, sizeof(S));

for (k=1;k<=2;k++)
	for (i=1;i<=2;i++)
		for (j=1;j<=2;j++)
			C[k][i]=( (C[k][i])%mod + ( (A[k][j]%mod)*(B[j][i]%mod) )%mod );
		
memcpy(A, S, sizeof(S));
}

int main() {
A[1][2]=1;		A[2][1]=1;		A[2][2]=1;
B[1][2]=1;		B[2][1]=1;		B[2][2]=1;
fscanf (f, "%d", &k);	
if (!k)		A[2][2]=0;
k--;

while (k)
{
	v[++i]=k%2;
	k/=2;
}

for (j=i-1;j>=1;j--)
{
	inmultire(A,A,S);
	if (v[j])
		inmultire(A,B,S);
}

fprintf (g, "%lld", A[2][2]%mod);
return 0;
}