#include <fstream>
#include <array>
using namespace std;
 
constexpr int mod = 666013;

using mat = array<array<unsigned long, 2>, 2>;

mat mult(const mat& lhs, const mat& rhs){
	static mat rez;
	for(int i = 0; i < 2; ++i){
		for(int j = 0; j < 2; ++j){
			rez[i][j] = 0;
			for(int k = 0; k < 2; ++k){
				rez[i][j] += (lhs[i][k] * rhs[k][j])%mod;
				rez[i][j] %= mod; } } }
	return rez; }

constexpr mat exp(const mat& e, const int x, const mat& rez = {1, 0, 0, 1}){
	return (x==0) ? rez : (x&1) ? exp(mult(e, e), x/2, mult(e, rez)) : exp(mult(e, e), x/2, rez); }

int main(){
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	int k;
	f >> k;
	g << exp(mat{1, 1, 1, 0}, k)[0][1] << '\n';
	return 0; }