重铸华农荣光 我辈义不容辞

Day 21(twenty-first)-卡特兰数

#include<iostream>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int qmi(int a,int k,int p)
{
    int ans=1;
    while(k)
    {
        if(k&1) ans=(ll)ans*a%p;
        k>>=1;
        a=(ll)a*a%p;
    }
    return ans;
}

int main()
{
    int n;
    cin>>n;

    int ans=1;
    int a=2*n,b=n;

    for(int i=a,j=1;i>a-b;i--,j++)
    {
        ans=(ll)ans*i%mod;
        ans=(ll)ans*qmi(j,mod-2,mod)%mod;
    }

    ans=(ll)ans*qmi(b+1,mod-2,mod)%mod;
    cout<<ans;
    return 0;
}