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

//#include "stdafx.h"

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

#define O2 m2x2{ {0, 0}, {0, 0} }
#define I2 m2x2{ {1, 0}, {0, 1} }


template <typename T, int N, int M>
class Matrix {
	T a[N][M];
public:
	Matrix() : a() {

	}

	Matrix(const std::initializer_list<std::initializer_list<T>>& list) : a() {
		auto il = list.begin();
		for (int i = 0; i < list.size(); ++i) {
			auto it = il->begin();
			for (int j = 0; j < il->size(); ++j) {
				a[i][j] = *it++;
			}
			il++;
		}

	}

	T* operator[](int i) {
		return a[i];
	}

	const T* operator[](int i) const {
		return a[i];
	}

};
typedef Matrix<int, 2, 2> m2x2;

template <class T, int N, int M, int K, int V>
Matrix<T, N, V> operator*(const Matrix<T, N, M>& a, const Matrix<T, K, V>& b) {
	Matrix<T, N, V> res;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < V; ++j) {
			for (int k = 0; k < V; ++k) {
				res[i][j] = (res[i][j] + 1ULL * a[i][k] * b[k][j]) % 666013;
			}
		}
	}

	return res;
}


template <class T, class U>
T log_pow(const T& x, const U& n) {
	if (n == 1)
		return x;
	if (n == 0)
		return T();

	if (n % 2 == 0)
		return log_pow(x * x, n / 2);
	return x * log_pow(x * x, (n - 1) / 2);
}

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

	m2x2 x{ { 1, 1 }, { 1, 0 } };
	int k;
	
	fin >> k;
	x = log_pow(x, k - 1);

	
	fout << x[0][0];
	
	return 0;
}