#include<fstream>
#include<iostream>

using namespace std;

typedef unsigned long long uint64;
const long MOD=666013;

uint64 **fibs;

void CreateMat(uint64 **&m)
{
	m = new uint64*[2];
	m[0] = new uint64[2];
	m[1] = new uint64[2];
}

void InitFibs(uint64 **fibs)
{
	fibs[0][0]=fibs[0][1]=fibs[1][0]=1;
	fibs[1][1]=0;
};

void MulMat(uint64 **a, uint64 **b, uint64 **c)
{
	c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
	c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
	
	c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
	c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
}

int main()
{
	int k;
	fstream fin("kfib.in",fstream::in);
	fstream fout("kfib.out",fstream::out);
	uint64 **s,**rez,**fibrez,**aux;
	CreateMat(fibs);
	InitFibs(fibs);
	CreateMat(s);
	InitFibs(s);
	CreateMat(rez);
	CreateMat(fibrez);
	fin>>k;
	k-=2;
	while(k)
	{
		if(k & 1)
		{
			MulMat(s,fibs,rez);
			aux=s;
			s=rez;
			rez=aux;
		}
		
		MulMat(fibs,fibs,fibrez);
		aux=fibs;
		fibs=fibrez;
		fibrez=aux;
		k>>=1;
	}
	
	fout<<s[0][0]<<"\n";
	return 0;
}