#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;

const char iname[] = "kfib.in";
const char oname[] = "kfib.out";


void mul(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] + ((((long long) A[i][k]) * B[k][j]) % 666013LL)) % 666013;
		}
	}
	memcpy(A, C, sizeof C);
}

void f(int Z[2][2], int K) {
	int R[2][2] = {{1, 0}, {0, 1}};

	for (int i = 30; i >= 0; -- i) {
		mul(R, R);
		if ((K >> i) & 1)
			mul(R, Z);
	}
	memcpy(Z, R, sizeof R);
}

int main(void) {
	int K;
	ifstream in(iname);
	assert(in >> K);
	assert(1 <= K && K <= 1000000000);
	in.close();

	int Z[2][2] = {{0, 1}, {1, 1}};
	f(Z, K - 1);
	ofstream out(oname);
	out << Z[1][1];
	out.close();
	return 0;
}