#include <cstdio>
#define MOD 666013
int k;
struct matrice  //matrice de ordin 2
{
	long long a, b, c, d;
};

matrice inmultire(matrice A, matrice B) //inmultire a doua matrici de ordin 2 , totul modulo MOD
{
	matrice aux;
	aux.a = (((A.a%MOD) * (B.a%MOD))%MOD + ((A.b%MOD) * (B.c%MOD))%MOD) %MOD;
	aux.b = (((A.a%MOD) * (B.b%MOD))%MOD + ((A.b%MOD) * (B.d%MOD))%MOD) %MOD;
	aux.c = (((A.c%MOD) * (B.a%MOD))%MOD + ((A.d%MOD) * (B.c%MOD))%MOD) %MOD;
	aux.d = (((A.c%MOD) * (B.b%MOD))%MOD + ((A.d%MOD) * (B.d%MOD))%MOD) %MOD;
	return aux;
}

matrice power(matrice Z, int p)
{
	if (p == 1) //caz elementar Z^1 = Z
		return Z;
		
	if (p % 2 == 1)	
		return inmultire(Z,	power(Z,p-1)); //Z^p = Z * Z ^ (p - 1)
	else
	{
		matrice B = power(Z, p/2);  //B = Z^(p/2)
		return inmultire(B, B); //Z^p = B*B
	}
}


int main()
{
	FILE *f = fopen("kfib.in", "r");
	fscanf(f, "%d", &k);
	fclose(f);
	f = fopen("kfib.out", "w");
	//f0 si f1 spearat
	if (k == 0)
	{
		fprintf(f, "0\n");
		return 0;
	}
	else
		if (k == 1)
		{
			fprintf(f, "1\n");
			return 0;
		}
		
	matrice Zk, Z;
	Z.a = 0, Z.b = Z.c = Z.d = 1;//matricea Z
	Zk = power(Z, k-1);//Zk = Z^(k-1)
	
	fprintf(f, "%lld", Zk.d);//raspunsul se afla in Zk.d
	fclose(f);
	
	return 0;
}