#include<fstream>
#define mdl 666013
using namespace std;

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


struct Matrice {
	int a[2][2];
};

Matrice Produs(Matrice A, Matrice B) {
	Matrice C;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			C.a[i][j] = 0;
			for (int k = 0; k < 2; ++k) {
				C.a[i][j] += A.a[i][k] * B.a[k][j];
				C.a[i][j] %= mdl;
			}
		}
	}
	return C;
}
Matrice Putere(Matrice A, int n) {
	if (n == 0) {
		Matrice C;
		C.a[0][0] = 1; C.a[0][1] = 0;
		C.a[1][0] = 0; C.a[1][1] = 1;
		return C;
	}
	else if (n == 1) return A;
	else {
		if (n % 2 == 0) {
			return Putere(Produs(A, A), n / 2);
		}
		else return Produs(A, Putere(Produs(A, A), n / 2));
	}
}

int main() {
	Matrice A;
	int a,k;
	fin >> k;
	A.a[0][0] = 0; A.a[0][1] = 1;
	A.a[1][0] = 1; A.a[1][1] = 1;

	Matrice Z = Putere(A, k-1);

	fout << Z.a[1][1];
	return 0;
}