카탈란 수 ( Catalan Number )

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10, M=1e9+7;
typedef long long ll;
ll inv[N]={0,1}, cat[N]={1,1};

int main(){
    int n;
    scanf("%d",&n);
    for(int i=2; i<N; ++i) inv[i]=inv[M%i]*(M-M/i)%M; // modulo inverse
    for(int i=2; i<N; ++i) cat[i]=cat[i-1]*(4*i%M-2)%M*inv[i+1]%M; // catalan numbers
}

C(i) = C(i-1) x (4i - 2)