#define MOD 666013

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

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

struct Matrice2x2
{
	int64_t a, b, c, d;
	
	Matrice2x2& operator*= (const Matrice2x2& other)
	{
		int _a = (((a * other.a) % MOD) + ((b * other.c) % MOD)) % MOD;
		int _b = (((a * other.b) % MOD) + ((b * other.d) % MOD)) % MOD;
		int _c = (((c * other.a) % MOD) + ((d * other.c) % MOD)) % MOD;
		int _d = (((c * other.b) % MOD) + ((d * other.d) % MOD)) % MOD;
		
		a = _a;
		b = _b;
		c = _c;
		d = _d;
		
		return (*this);
	}
};

Matrice2x2 XlaN(const Matrice2x2& X, int64_t N);

int main()
{
	int64_t k;
	
	fin >> k;
	
	Matrice2x2 Z;
	Z.a = 0;
	Z.b = Z.c = Z.d = 1;
	
	Matrice2x2 res = XlaN(Z, k - 1);
	
	fout << res.d;
	
	fin.close();
	fout.close();
	return 0;
}

Matrice2x2 XlaN(const Matrice2x2& X, int64_t N)
{
	if (N == 0)
	{
		Matrice2x2 res;
		
		res.a = res.d = 1;
		res.b = res.c = 0;
		
		return res;
	}
	
	Matrice2x2 P = XlaN(X, N / 2);
	P *= P;
	
	if ((N % 2) == 1)
	{
		P *= X;
	}
	
	return P;
}