分析

$$ 卡特兰数：f(n)=\frac{C_{2n}^{n}}{n+1}= C_{2n}^{n}-C_{2n}^{n-1} $$

样例：f(3)=5

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int n;
LL a,b;
LL qmi(LL a,LL k)
{
    LL ans=1;
    while(k)
    {
       if(k&1) ans=ans*a%mod;
       a=a*a%mod;
       k>>=1; 
    }
    return ans;
}
LL res=1;
int main()
{
    cin>>n;
    a=2*n,b=n;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=(res*j)%mod;
        res=res*qmi(i,mod-2)%mod;
    }
    res=res*qmi(n+1,mod-2)%mod;
    cout<<res;
    return 0;
}