#include <cstdio>
#include <cstring>

#define MOD 666013

int Z[3][3], F[3][3], k, exp;

void mult (int A[][3], int B[][3], int n, int m) {
	
	int i, j, k;
	long long C[3][3];
	
	memset (C, 0, sizeof (C));
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			for (k = 1; k <= n; k++) {
				C[i][j] += (1LL * A[i][k] * B[k][j]) % MOD;
				if (C[i][j] >= MOD)
					C[i][j] -= MOD;
			}
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			B[i][j] = C[i][j];
}

int main () {
	
	freopen ("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	
	scanf ("%d", &k);
	
	F[1][1] = 0, F[2][1] = 1;
	
	exp = k - 1;
	
	Z[1][1] = 0, Z[1][2] = 1;
	Z[2][1] = 1, Z[2][2] = 1;
	
	while (exp > 0) {
		if (exp & 1)
			mult (Z, F, 2, 1);
		
		mult (Z, Z, 2, 2);
		exp >>= 1;
	}
	
	if (exp == -1)
		printf ("0");
	else
		printf ("%d", F[2][1]);
	
	return 0;
}