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

constexpr int mod = 666013;

template <typename T, int N, int M>
using mat = array<array<T, M>, N>;

template <typename T, unsigned long N, unsigned long M, unsigned long K>
mat<T, K, M> operator*(const mat<T, N, M>& A, const mat<T, K, N>& B){
	static mat<T, K, M> 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(mat<unsigned long, 2, 2>{1, 1, 1, 0},
		k, mat<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; }