如何求第n个卡特兰数对mod取模mod=1e9c++

卡特兰数公式：

$C_n=\frac{C_{2n}^n}{n+1}$

可以用递推式求解卡特兰数：

$C_0=1$

$C_{n+1}=\frac{2(2n+1)}{n+2}C_n$

对于取模操作，需要注意以下两点：

1. 在求组合数时，需要使用Lucas定理，将组合数分解为多个小的组合数的积，再对每个小组合数取模，最后对积取模。

2. 在递推过程中，需要将每一步的结果对取模数取模，避免出现溢出。

具体代码如下：