#include <cstdio>
long long Res[3][3], k;
#define NR 666013

void inmultire(long long A[3][3], long long B[3][3])
{
	long long C[3][3];
	C[1][1] = (A[1][1] * B[1][1] + A[1][2] * B[2][1]) % NR;
	C[1][2] = (A[1][1] * B[1][2] + A[1][2] * B[2][2]) % NR;
	C[2][1] = (A[2][1] * B[1][1] + A[2][2] * B[2][1]) % NR;
	C[2][2] = (A[2][1] * B[1][2] + A[2][2] * B[2][2]) % NR;
	A[1][1] = C[1][1];
	A[1][2] = C[1][2];
	A[2][1] = C[2][1];
	A[2][2] = C[2][2];
}
void lgpow(long long M[3][3])
{
    long long p = 1;
	Res[1][1] = 1;
	Res[2][2] = 1;
	while(p <= k)
	{
		if(p & k)
		{
			inmultire(Res, M);

		}
		inmultire(M, M);
		p = p << 1;
	}
}
int main()
{
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%lld", &k);
	long long M[3][3] = {{0, 0, 0}, {0, 0, 1}, {0, 1, 1}};
	lgpow(M);
    printf("%d", Res[2][1]);
	return 0;
}