#include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #define debug(x) cerr << #x << " = " << (x) << endl; #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 20000010 ll fac[SIZE*2] = {}; ll factorial(int n,int M){ return fac[n]; } ll power(int k,int n,int M){ if(n==0) return 1; if(n==1) return (ll)k; ll ret = power(k,n/2,M); ret=(ret*ret)%M; if(n%2==1) ret=(ret*k)%M; return ret; } //nCm nPm nHm (mod M) /*Combination*/ int C(int n,int m,int M){ if(n> n; fac[0] = 1; for(int i=1;i<=n*2;i++){ fac[i] = (fac[i-1]*i)%mod; } ll p = power(2,mod-2, mod); ll ans = fac[n*2]; for(int i=0;i