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

constexpr unsigned long long mod = 666013;

template <typename T, size_t n, size_t m>
using mat = array<array<T, m>, n>;

template <typename T, size_t n, size_t m, size_t p>
mat<T, n, m> operator*(const mat<T, n, p>& a, const mat<T, p, m>& b){
	static mat<T, n, m> rez;
	for(size_t i = 0; i < n; ++i){
		for(size_t j = 0; j < m; ++j){
			rez[i][j] = 0;
			for(size_t k = 0; k < p; ++k){
				rez[i][j] += (a[i][k] * b[k][j])%mod;
				rez[i][j] %= mod; } } }
	return rez; }

template <typename T>
T exp(const T e, const int x, const T rez){
	return x ? exp(e*e, x/2, (x&1) ? (rez*e) : (rez)) : (rez); }

int kfib(const unsigned long long x){
	return exp(mat<unsigned long long, size_t(2), size_t(2)>{ { {1ull, 1ull}, {1ull, 0ull} } },
		x,
		mat<unsigned long long, size_t(2), size_t(2)>{ { {1ull, 0ull}, {0ull, 1ull} } })[0][1]; }

int main(){
	ifstream f("kfib.in");
	unsigned long long k = 0;
	f >> k;
	ofstream g("kfib.out");
	g << kfib(k) << '\n';
	return 0; }