#include #define int long long #define vec vector #define forn(i, n) for(int i = 0;i>(a)[i] #define write(a) forn(i, (a).size()) cout<<(a)[i] << " "; cout << "\n"; using namespace std; int mod = 1e9+7; vec fact; //vec r; int binpow(int n, int k){ if(k==0){ return 1; } if(k==1) return n; if(k%2){ return (binpow(n,k-1)*n)%mod; } int bp = binpow(n,k/2); return (bp*bp)%mod; } int r(int x){ return binpow(x,mod-2); } int add_mod(int x){ while(x<0) x+=mod; while(x>=mod) x-=mod; return x; } int get_seg(int len, int cnt1){ int cnt0 = len-cnt1; int ans = fact[len]; ans*=r(fact[cnt1]); ans%=mod; ans*=r(fact[cnt0]); ans%=mod; return ans; } int C(int n, int k){ int ans = fact[n]; ans*=r(fact[k]); ans%=mod; ans*=r(fact[n-k]); ans %= mod; return ans; } void solve(){ int n; cin>>n; fact.resize(4*n+5); fact[0] = 1; for(int i=1;i