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