#include <stdio.h>
#define M 666013
#define LIM_PRE 30

int n;

long long a[2][2] = {{0, 1}, {1, 1}};
long long O[2][2] = {{0, 0}, {0, 0}};
long long I[2][2] = {{1, 0}, {0, 1}};

long long puteri[LIM_PRE][2][2];

inline void citeste()
{
	FILE* fi = fopen("kfib.in", "r");
	fscanf(fi, "%d", &n);
	fclose(fi);
}

inline void scrie()
{
	FILE* fo = fopen("kfib.out", "w");
	fprintf(fo, "%lld\n", a[1][1]);
	fclose(fo);
}

void copiaza_matrice(long long destinatie[2][2], long long sursa[2][2])
{
	destinatie[0][0] = sursa[0][0];
	destinatie[0][1] = sursa[0][1];
	destinatie[1][0] = sursa[1][0];
	destinatie[1][1] = sursa[1][1];
}

void inmulteste(long long destinatie[2][2], long long sursa[2][2])
{
	long long cd[2][2], cs[2][2]; //copie destinatie
	copiaza_matrice(cd, destinatie);
	copiaza_matrice(cs, sursa);
	copiaza_matrice(destinatie, O);
	
	destinatie[0][0] = (cd[0][0] * cs[0][0] + cd[0][1] * cs[1][0]) % M;
	destinatie[0][1] = (cd[0][0] * cs[0][1] + cd[0][1] * cs[1][1]) % M;
	destinatie[1][0] = (cd[1][0] * cs[0][0] + cd[1][1] * cs[1][0]) % M;
	destinatie[1][1] = (cd[1][0] * cs[0][1] + cd[1][1] * cs[1][1]) % M;
}

void scrie_matrice(long long matrice[2][2])
{
	return;
	fprintf(stderr, "%lld %lld\n%lld %lld\n***\n", matrice[0][0], matrice[0][1], matrice[1][0], matrice[1][1]);
}

void precalcul()
{
	long long aux[2][2];
	copiaza_matrice(aux, a);
	int i;
	for(i = 0; i < LIM_PRE; ++i)
	{
		copiaza_matrice(puteri[i], aux);
		scrie_matrice(puteri[i]);
		inmulteste(aux, aux);
	}
}

void detkfib()
{
	int p = n - 1, i = 0;
	copiaza_matrice(a, I);
	while(p)
	{
		if(p % 2) inmulteste(a, puteri[i]);
		i++;
		p /= 2;
	}
}

int main()
{
	citeste();
	precalcul();
	detkfib();
	scrie();
	return 0;
}