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

matrice inmultire(matrice A, matrice B)
{
	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)
		return Z;
		
	if (p % 2 == 1)	return inmultire(Z,	power(Z,p-1));
	else
	{
		matrice B = power(Z, p/2);
		return inmultire(B, B);
	}
}


int main()
{
	FILE *f = fopen("kfib.in", "r");
	fscanf(f, "%d", &k);
	fclose(f);
	f = fopen("kfib.out", "w");
	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;
	Zk = power(Z, k-1);
	fprintf(f, "%lld", Zk.d);
	fclose(f);
	return 0;
}