因式分解法求卡特兰数取模1e91e9不是质数

首先，我们知道卡特兰数的递推公式为：

C(n) = (2n)! / ((n+1)! * n!)

由于题目要求对1e9取模，我们需要对上式中的所有因子都取模。但是，1e9不是质数，因此我们不能直接使用逆元求解。这时，我们可以使用扩展欧几里得算法来求解。

具体来说，我们需要求解(n+1)!和n!在模1e9意义下的乘法逆元，然后将这两个逆元相乘，再将结果乘以(2n)!，最后再对1e9取模即可。

下面给出代码实现：

def ext_gcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, d = ext_gcd(b, a % b)
    return y, x - a // b * y, d

def mod_inv(a, n):
    x, y, d = ext_gcd(a, n)
    if d == 1:
        return (x % n + n) % n
    else:
        return -1

def catalan(n):
    mod = 10**9
    fact = [1] * (2*n+1)
    for i in range(1, 2*n+1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [0] * (n+1)
    for i in range(n+1):
        inv_fact[i] = mod_inv(fact[i], mod)
    res = fact[2*n] * inv_fact[n+1] % mod * inv_fact[n] % mod
    return res

n = int(input())
print(catalan(n))

时间复杂度分析：该算法的时间复杂度为O(nlogn)，其中n为卡特兰数的项数。