给定n个0和n个1,它们将按照某种顺序排成长度为2n的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。
输出的答案对109+7取模。
输入格式
共一行,包含整数n。
输出格式
共一行,包含一个整数,表示答案。
数据范围
1≤n≤105
输入样例:
3
输出样例:
5
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qsm(ll a,ll k,ll p) //快速幂求逆元;
{
ll res=1;
while(k)
{
if(k&1)res=res*a%p;
k>>=1;
a=a*a%p;
}
return res;
}
int main()
{
ll n;
cin>>n;
ll a=2*n,b=n;
ll res=1;
for(ll i=a;i>a-b;i--)res=res*i%mod;
for(ll i=1;i<=b;i++)res=res*qsm(i,mod-2,mod)%mod;
res=res*qsm(b+1,mod-2,mod)%mod;
cout<<res<<endl;
}