卡特兰数求解与取模 - Python 实现

可以使用递推公式求解第 n 个卡特兰数，然后再除以 n+1 取模，代码如下：

n = int(input())
mod = 10**9

# 初始化卡特兰数列表
catalan = [1] * (n+1)

# 递推计算卡特兰数
for i in range(1, n+1):
catalan[i] = catalan[i-1] * (4*i-2) // (i+1) % mod

# 输出第 n 个卡特兰数除以 (n+1) 取模的结果
print(catalan[n] * pow(n+1, mod-2, mod) % mod)

这里使用了求逆元的方法来计算除以 n+1 的模反元素，从而实现除法取模。