#include <cstdio>
#include <vector>
#include <string>
#include <vector>
using namespace std;

const int NMAX = 2;
const int MOD = 666013;

int N;

vector<vector<int>> firstTwoTerms = {{1, 1}, {0, 0}};
vector<vector<int>> transition = {{0, 1}, {1, 1}};

vector<vector<int>> mul(vector<vector<int>> firstMatrix, vector<vector<int>> secondMatrix) {
	vector<vector<int>> result(NMAX, vector<int>(NMAX, 0));
	for (int l = 0; l < NMAX; l++) {
		for (int c = 0; c < NMAX; c++) {
			long long curr = 0;
			for (int k = 0; k < NMAX; k++) {
				curr += 1LL * firstMatrix[l][k] * secondMatrix[k][c];
			}
			result[l][c] = curr % MOD;
		}
	}

	return result;
}

vector<vector<int>> neutralElement() {
	vector<vector<int>> result(NMAX, vector<int>(NMAX, 0));
	for (int i = 0; i < NMAX; i++) {
		result[i][i] = 1;
	}

	return result;
}

vector<vector<int>> lgput(vector<vector<int>> matrix, int exponent) {
	vector<vector<int>> result = neutralElement();
	vector<vector<int>> matrixPowTwo = matrix;

	for (int bitIdx = 0; (1 << bitIdx) <= exponent; bitIdx++) {
		if (exponent & (1 << bitIdx)) {
			result = mul(result, matrixPowTwo);
		}
		matrixPowTwo = mul(matrixPowTwo, matrixPowTwo);
	}

	return result;
}

int getFibTerm(int N) {
	vector<vector<int>> result = firstTwoTerms;

	vector<vector<int>> transitionNMinusOneTimes = lgput(transition, N - 1);
	result = mul(result, transitionNMinusOneTimes);

	return result[0][0];
}

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	scanf("%d", &N);
	printf("%d\n", getFibTerm(N));
	return 0;
}