卡特兰数裸题

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n;

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

int main(){
    cin>>n;
    int a=2*n,b=n;
    int res=1;

    for(int i=1,j=a;i<=b;i++,j--){
        res=(ll)res*j%mod;
        res=(ll)res*qsm(i,mod-2,mod)%mod;
    }
    res=(ll)res*qsm(n+1,mod-2,mod)%mod;

    cout<<res<<endl;

}