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

constexpr unsigned long int mod = 666013;

template <typename T, unsigned long int n, unsigned long int m>
using mat = array<array<T, m>, n>;

template <typename T, unsigned long int n, unsigned long int m, unsigned long int 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(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			rez[i][j] = 0;
			for(int 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, 2, 2>{ { {1, 1}, {1, 0} } },
		x,
		mat<unsigned long long, 2, 2>{ { {1, 0}, {0, 1} } })[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; }