不得不说a,这题是真的奇葩,手算了样例蒙了一个结论,套上组合数II的板子,还真就AC了
结论题,结果等于$ C(n*2,n)-C(n*2,n-1) $,至于为什么,咱也不知道,咱也不敢问(doge
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=2e5+5,mod=1e9+7;
int n,fac[MAX],inv[MAX];
int ksm(int x,int y){
int cnt=1;
while(y){
if(y&1) cnt=cnt*x%mod;
x=x*x%mod;y=y>>1;
}return cnt;
}
int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init(){
fac[0]=inv[0]=1;
for(int i=1;i<MAX;i++){
fac[i]=fac[i-1]*i%mod;
inv[i]=inv[i-1]*ksm(i,mod-2)%mod;
}
}
signed main(){
ios::sync_with_stdio(NULL);
cin.tie(0);cout.tie(0);
init();cin>>n;
cout<<(C(n*2,n)-C(n*2,n-1))%mod<<endl;
return 0;
}