给定 n个 0 和 n个 1，它们将按照某种顺序排成长度为 2n的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0的个数都不少于 1的个数的序列有多少个。
输出的答案对 1e9+7取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤1e5
输入样例：
3
输出样例：
5
思路：
将01排序问题转化为卡特兰数问题，先给出公式：
01排序相当于在下图从（0，0）走到（6，6）而不经过红线的方法数，不经过红线的方法树有对称线可知，（0，0）到（6，6）和（0，0）到（5，7）方法数是一样的，由此此问题可以使用卡特兰数公式。
#include <iostream> using namespace std; const int mod=1e9+7; typedef long long ll; int qmi(int a,int k,int p){ int res=1; while(k){ if(k&1)res=(ll)res*a%p; a=(ll)a*a%p; k>>=1; } return res; } int main(){ int n; cin>>n; int a=2*n,b=n; int res=1; for(int i=a;i>a-b;i--)res=(ll)res*i%mod; for(int i=1;i<=b;i++)res=(ll)res*qmi(i,mod-2,mod)%mod; res=(ll)res*qmi(n+1,mod-2,mod)%mod; cout<<res<<endl; }
