#include <fstream>
using namespace std;
struct Matrice{
	unsigned long long a,b,c,d;
	Matrice operator *(Matrice x)
	{
		Matrice result;

		result.a = a * x.a + b * x.c;
		result.b = a * x.b + b * x.d;
		result.c = c * x.a + d * x.c;
		result.d = c * x.b + d * x.d;
		return result;
	}

	Matrice operator %(unsigned long long m)
	{
		Matrice temp = *this;
		
		temp.a = a % m;
		temp.b = b % m;
		temp.c = c % m;
		temp.d = d % m;

		return temp;
	}
};

struct Vector
{
	unsigned long long x, y;

	Vector operator *(Matrice m)
	{
		Vector res;

		res.x = x * m.a + y * m.c;
		res.y = x * m.b + y * m.d;

		return res;
	}
};


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

int main ()
{
	int n, m = 666013;
	fin>>n;
	Matrice rez, temp;
	Vector F;
	F.x = 0;
	F.y = 1;
	
	temp.a=0;
	temp.b=1;
	temp.c=1;
	temp.d=1;
	
	rez.a = 1;
	rez.b = 0;
	rez.c = 0;
	rez.d = 1;
	


	while(n!=0)
	{
		if(n%2!=0)
			rez=(rez*temp)%m;
		temp = (temp * temp) % m;
		n /= 2;

	}

	fout << (F * rez).x % m << endl;
	return 0;
}