圆内连弦 - 卡特兰数

知识点
总方案数是其中表示每次选择2个，除以表示这n次选择没有先后

而可行数是圆内连弦的个数，是个卡特兰数，不会的可以去上面的博客学习一下卡特兰数以及在圆内连弦的解法

化简总方案数

卡特兰数为

那么答案就是,求(n + 1)! % mod在mod下的逆元乘以 % mod即可

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
ll pow(ll a, ll b, ll p){
    ll ans = 1; a %= p;
    while(b){
        if(b & 1)ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int n, fac, f[N];
int main(){
    scanf("%d", &n);
    fac = 1;
    for(int i = 1; i <= n + 1; i++)
        fac = 1ll * fac * i % mod;
    printf("%lld\n", pow(2, n, mod) * pow(fac, mod - 2, mod) % mod);
    return 0;
}