因式分解法求卡特兰数取模

卡特兰数的递推式为：

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

可以通过因式分解法对该递推式进行简化：

$$C_n=\frac{(2n)!}{(n+1)!n!}=\frac{(2n)(2n-1)\cdots(n+2)(n+1)}{n(n-1)\cdots2\cdot1}$$

$$=\frac{2(2n-1)}{n+1}\cdot\frac{(2n-2)!}{(n-1)!n!}=\frac{2(2n-1)}{n+1}C_{n-1}$$

因此，我们可以用以下代码实现卡特兰数取模：

def catalan(n, mod):
    c = 1
    for i in range(n):
        c = c * (4 * i + 2) % mod
        c = c * pow(i + 2, mod - 2, mod) % mod
    return c

其中，pow(i + 2, mod - 2, mod) 表示将 $i+2$ 模 $mod$ 意义下的乘法逆元，可以使用费马小定理或扩展欧几里得算法来求解。