Catalen-No.cpp

Fatal Eagle has had it enough with Arjit aka Mr. XYZ who's been trying to destroy the city from the first go. He cannot tolerate all this nuisance anymore. He's... tired of it. He decides to get rid of Arjit and his allies in a war. He knows that Arjit has N people fighting for him, so he brings his own N people in the war to face him. (So, there will be 2 * N people fighting in this war!)

He knows for him to win the war against his enemy, members of his army should be present before the members of Arjit come up in the battlefield - that is to say, whenever a member of Arijt's army comes in the battlefield, there should already be a member of his own army there to handle him. (In short, the number of his army members should never be less than the number of Arjit's army members in the field!)

If he figures out the number of ways such such sequences can be formed, the good will be able to conquer evil yet again. Help Fatal Eagle in figuring it out to defeat Arjit - once and for all.

Input format:
There is only one integer in the only line of the input, denoting the value of N.

Output format:
Print the number of valid sequences. Since the output might be very big, print it modulo 109+9.

Constraints:
1 <= N <= 105
SAMPLE INPUT

3

SAMPLE OUTPUT

5

Explanation

Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

Cn= ( 2n )! / ( (n+1) ! ( n ) ! )

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll m=1e9+9;
    ll fact(ll n)
    {
    	ll f=1,i;
    	for(i=2;i<=n;i++)
    	{
    		f=(f%m*i%m)%m;
    	}
    	return f;
    }
    ll inv(ll a,ll n)
    {
    	if(n==0)
    	return 1;
    	if(n%2==0)
    	{
    		return inv((a*a)%m,n/2);
    	}
    	else
    	return (a*inv((a*a)%m,(n-1)/2))%m;
    }
     
    int main()
    {
    	ll n,i,j,k;
    	cin>>n;
    	ll f1=fact(2*n);
    	ll f2=fact(n+1);
    	ll f3=fact(n);
    	ll f4=inv(f2,m-2);
    	ll f5=inv(f3,m-2);
    	ll ans=(f1%m*f4%m*f5%m)%m;
        cout<<ans<<endl;
        return 0;
    }