#include <bits/stdc++.h>

const int MOD = 666013;

inline void multiply(int A[2][2], int B[2][2]) {
	int C[2][2];

	for (int i = 0 ; i < 2 ; ++i) {
		for (int j = 0 ; j < 2 ; ++j) {
			C[i][j] = 0;

			for (int k = 0 ; k < 2 ; ++k) {
				C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
			}
		}
	}

	memcpy(A, C, sizeof(C));
}

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	int n;
	scanf("%d", &n);
	int Z[2][2] = {{0, 1}, {1, 1}};
	int In[2][2] = {{1, 0}, {0, 1}};

	while (n) {
		if (n & 1) {
			multiply(In, Z);
		}

		n >>= 1;
		multiply(Z, Z);
	}

	printf("%d\n", In[0][1]);
	return 0;
}