1. 问题描述：
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。输出的答案对 10 ^ 9+7 取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1 ≤ n ≤ 10 ^ 5
输入样例：
3
输出样例：
5
2. 思路分析：
分析题目可以知道这道题目属于卡特兰数的裸题，其中一个比较有技巧的方法将其转换为直角坐标系中的路径，向右走为0，向下走为1，红线以下的路径是合法的，以n = 6为例，如下图所示，任意一条从(0，0)到(6，6)的非法路径做关于红线的对称，最终都会对应1条从(0，0)到(5，7)的路径，更一般化来说对于任意一条从(0，0)到(n，n)的路径的非法路径都可以做关于红线的对称最终得到一条从(0，0)到(n - 1，n + 1)的路径，则总共路径的方案数目为2n个数中选n个数的方案，不合法的方案数目2n个数中选n - 1个数，所以合法方案数目为res = （C2nn - C2nn-1）= C2nn / (n + 1)，使用组合数的公式求解即可，而且由于p = 10 ^ 9 + 7是一个质数而且n小于p所以由费马小定理可以知道 / m! = * infact(m!)，m!的 p - 2次方就是m!的逆元。
3. 代码如下：
class Solution:
# 快速幂
def quickPower(self, a: int, b: int, mod: int):
res = 1
while b > 0:
if b & 1:
res = res * a % mod
a = a * a % mod
b >>= 1
return res
# 使用卡特兰数的公式计算即可
def process(self):
n = int(input())
p = 10 ** 9 + 7
res = 1
for i in range(2 * n, n, -1):
res = res * i % p
# 求解n!的逆元
for i in range(1, n + 1):
res = res * self.quickPower(i, p - 2, p) % p
# 乘以n + 1的逆元
return res * self.quickPower(n + 1, p - 2, p) % p
if __name__ == "__main__":
print(Solution().process())
