#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];
long long n,m,x;
int i,j,v[1000];

long long cmmdc(long long a, long long b) {
long long r=a%b;
while (r)
{
	a=b;
	b=r;
	r=a%b;
}
return b;
}

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() {
fscanf (f, "%lld", &n);
x=cmmdc(0,n)-1;

A[1][2]=A[2][1]=A[2][2]=B[1][2]=B[2][1]=B[2][2]=1;

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

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

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