#include<fstream>
#define MOD 666013
#define NMAX 3

using namespace std;

long long a[NMAX][NMAX], b[NMAX][NMAX], c[NMAX][NMAX];
int n;

ifstream f("kfib.in");
ofstream g("kfib.out");

void INITIALIZEAZA()
{
	a[1][1]=0;
	a[1][2]=a[2][1]=a[2][2]=1;
	c[1][1]=0;
	c[1][2]=c[2][1]=c[2][2]=1;
	b[1][1]=b[1][2]=1;
	b[2][1]=b[2][2]=0;
}

void INMULTESTE(long long a[NMAX][NMAX], long long b[NMAX][NMAX])
{
	int v1, v2, v3, v4;
	v1=(a[1][1]*b[1][1])%MOD+(a[1][2]*b[2][1])%MOD;
	v2=(a[1][1]*b[1][2])%MOD+(a[1][2]*b[2][2])%MOD;
	v3=(a[2][1]*b[1][1])%MOD+(a[2][2]*b[1][2])%MOD;
	v4=(a[2][1]*b[2][1])%MOD+(a[2][2]*b[2][2])%MOD;
	a[1][1]=v1%MOD; a[1][2]=v2%MOD; a[2][1]=v3%MOD; a[2][2]=v4%MOD;
}

void KFIB(int n)
{
	if (n!=1)
	if (n%2==1) KFIB(n-1), INMULTESTE(a, c);
	else
	{
		KFIB(n/2);
		INMULTESTE(a, a);
	}
}


int main()
{
	f>>n;
	INITIALIZEAZA();
	KFIB(n+1);
	INMULTESTE(a, b);
	g<<a[1][1]<<"\n";
	f.close();
	g.close();
	return 0;
}