#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

constexpr int MOD = 666013;

static inline void matrix_multiply(int A[2][2], int B[2][2], int C[2][2]) {
	C[0][0] = ((1LL * A[0][0] * B[0][0]) % MOD + (1LL * A[0][1] * B[1][0]) % MOD) % MOD;
	C[0][1] = ((1LL * A[0][0] * B[0][1]) % MOD + (1LL * A[0][1] * B[1][1]) % MOD) % MOD;
	C[1][0] = ((1LL * A[1][0] * B[0][0]) % MOD + (1LL * A[1][1] * B[1][0]) % MOD) % MOD;
	C[1][1] = ((1LL * A[1][0] * B[0][1]) % MOD + (1LL * A[1][1] * B[1][1]) % MOD) % MOD;
}

static inline void matrix_copy(int A[2][2], int B[2][2]) {
	A[0][0] = B[0][0];
	A[0][1] = B[0][1];
	A[1][0] = B[1][0];
	A[1][1] = B[1][1];
}

static inline void matrix_fastpow(int A[2][2], int n, int B[2][2]) {
	int C[2][2];
	for (; n; n >>= 1) {
		if (n & 1) {
			matrix_multiply(A, B, C);
			matrix_copy(B, C);
		}
		matrix_multiply(A, A, C);
		matrix_copy(A, C);
	}
}

int N;

int main() {
	fin >> N;

	int A[2][2] = { 1, 1, 1, 0 };
	int B[2][2] = { 1, 0, 0, 1 };
	matrix_fastpow(A, N, B);

	fout << B[0][1];
	return 0;
}