// ConsoleApplication4.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <fstream>
#include <cstring>
using namespace std;

#define O2 {{0, 0}, {0, 0}}
typedef int m2x2[2][2];
typedef int m1x2[1][2];

void mul(m2x2 a, m2x2 b, m2x2 c) {
	m2x2 aux = O2;
	for (int i = 0; i < 2; ++i)
	for (int j = 0; j < 2; ++j)
	for (int k = 0; k < 2; ++k) {
		aux[i][j] = (aux[i][j] + 1ULL * a[i][k] * b[k][j]) % 666013;
	}
	memcpy(c, aux, sizeof(m2x2));
}

void log_pow(m2x2 x, int n) {
	if (n <= 1)
		return;
	if (n % 2 == 0) {
		mul(x, x, x);
		log_pow(x, n / 2);
	} else {
		m2x2 aux;
		memcpy(aux, x, sizeof(m2x2));
		mul(x, x, x);
		log_pow(x, (n - 1) / 2);
		mul(x, aux, x);
	}

}

int main() {
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	m2x2 a = {
		{ 1, 1 },
		{ 1, 0 }
	};
	int k;
	fin >> k;

	log_pow(a, k - 1);
	fout << a[0][0];

	
	return 0;
}