#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>> neutralElement = {{1, 0}, {0, 1}};

void 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;
		}
	}

	firstMatrix = result;
}

void 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)) {
			mul(result, matrixPowTwo);
		}
		mul(matrixPowTwo, matrixPowTwo);
	}

	matrix = result;
}

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

	lgput(transition, N - 1);
	mul(result, transition);

	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;
}