#include <stdio.h>
#define MOD 9999991
int n,a=1,b=1;
int main()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	scanf("%d",&n);
	if (n==1)
	{
		printf("1\n");
		return 0;
	}
	int i,c;
	for (i=3; i<=2*n-1; i++)
	{
		c=a+b;
		if (c>=MOD)
			c-=MOD;
		a=b; b=c;
	}
	printf("%d\n",b);
	return 0;
}