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

constexpr int mod = 666013;

template <typename T, unsigned long N, unsigned long M, unsigned long K>
array<array<T, M>, K> operator*(const array<array<T, M>, N>& A, const array<array<T, N>, K>& B){
	static array<array<T, M>, K> rez;
	for(int k = 0; k < K; ++k){
		for(int m = 0; m < M; ++m){
			rez[k][m] = T(0);
			for(int n = 0; n < N; ++n){
				rez[k][m] += (A[n][m] * B[k][n])%mod;
				rez[k][m] %= mod; } } }
	return rez; }

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

int kfib(const int k){
	return exp(array<array<unsigned long, 2>, 2>{1, 1, 1, 0},
		k, array<array<unsigned long, 2>, 2>{1, 0, 0, 1})[0][1]; }

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