题目来源：https://codeforces.com/contest/1999/problem/F
//
题意：给长度为n的01字符串，求每个长度为k的子序列串（不连续）的中位数总和。
//
思路：n的范围为2e5，“我也不会非暴力求所有子序列啊”。先理解下什么是中位数吧，就是对于有序的中间数字，奇数就是（k+1）/2。也只有中位数是1的子序列才有贡献值。
用c0表示0的个数，c1表示1的个数，取1的个数为x，则取0的个数就是（k-x），当1的个数>=（k+1）/2的时候，中位数才是1。所以总贡献度等于 c1取x个1的总方案 * 在c0中取（k-x）的总方案，（组合数）。
这里就设计到了组合数的板子，快速幂求逆元，预处理：线性递推阶层逆元。（a/b）%Mod==(a(b^(mod-2)))%Mod，前提mod为质数。
组合数在x中取y个数： 【!x / !y * !(x-y)】 == 【!x * (!y^(Mod-2)) * (!(x-y)^(Mod-2))】 == 【f[x] * inv[y] * inv[x-y]】。
inv表示阶层逆元，inv[i]=f[i]^(mod-2)，线性递推inv：inv[i]=(inv[i+1](i+1))//右到左递推
//
题解：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
const int N=2e5+5;
int f[N],inv[N];//f：阶层。inv：阶层逆元，inv[i]=f[i]^(mod-2)
int qower(int x,int y){
int ans=1;
while(y){
if(y&1){ans=(ans*x)%Mod;}
x=(x*x)%Mod;
y/=2;
}
return ans%Mod;
}
void init(){//预处理阶乘，阶乘逆元
f[0]=f[1]=1;
for(int i=2;i<=N-5;i++){//预处理阶乘
f[i]=(f[i-1]*i)%Mod;
}
inv[N-5]=qower(f[N-5],Mod-2);//线性递推阶乘逆元
for(int i=N-6;i>=0;i--){
inv[i]=(inv[i+1]*(i+1))%Mod;//inv[i]=f[i]^(mod-2)
}
}
int C(int x,int y){//x中取y（x>=y）
if(y>x){return 0;}
return ((f[x]*inv[y])%Mod*inv[x-y])%Mod;// !x / !y * !(x-y)==!x * (!y^(Mod-2)) * (!(x-y)^(Mod-2))==f[x]*inv[y]*inv[x-y]
}
void solve(){
int n,k,x;
cin>>n>>k;
int c0=0,c1=0;
for(int i=1;i<=n;i++){
cin>>x;
if(x){c1++;}
else{c0++;}
}
//当1的个数>=(k+1)/2的时候，就有1的贡献。1的数量为x，则0的数量为k-x
//总贡献：在1的数量里取x的总方案 * 在0的数量里取（k-x）的总方案：(x，c1) * ((k-x)，c0)
int ans=0;
for(int i=(k+1)/2;i<=k;i++){
ans=(ans+(C(c1,i)*C(c0,k-i)%Mod))%Mod;
}
cout<<ans<<'\n';
}
signed main()
{
init();
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}