#include <stdio.h>
#include <math.h>
#define MOD 666013
double power(double x, long p)
{
	long i;
	double rez=1.0;
	for (i=1; i<=p; i++) rez*=x;
	return rez;
}
long rotunjire (double x)
{
	long mic,mare;
	mare=ceil(x);
	mic=floor(x);
	if (mare-x>x-mic) return long(mic);
	else return long(mare);
}
long N;
int main ()
{
	FILE *f,*g;
	f=fopen("kfib.in", "r");
	g=fopen("kfib.out", "w");
	fscanf(f, "%d", &N);
	long long rezultat=1;
	rezultat=rotunjire((1/sqrt(5))*(power((1+sqrt(5))/2,N)-(1/sqrt(5))*power((1-sqrt(5))/2,N)))%MOD;
	fprintf(g, "%d", rezultat);
	fclose(f); fclose(g);
	return 0;
}