#include <iostream>
#include <cstring>
using namespace std;
#define mset(x) memset(x,0,sizeof(x))
typedef long long ll;
const ll p=1000000007;
const ll ti=500000004;
ll k;
ll n,t;
ll fr[300000],uf[300000],a[300000],b[300000],sg[300000];//fr[i]=i!,uf[i]=(k+1)(k+2)...(k+i),sg[i]=g(i)+g(i+1)+...+g(t)
string S;
ll qpow(ll x,ll y,ll r){
    while(y){
        if(y&1){
            r*=x;
            r%=p;
        }
        x*=x;
        x%=p;
        y/=2;
    }
    return r;
}
ll C(ll x){//C(k+x,k)
    if(x<0){
        return 0;
    }
    return qpow(fr[x],p-2,uf[x]);
}
ll f(ll ta){
    ll tmp=C(b[ta]-1)-C(a[ta]-1);
    return qpow(ti,ta,tmp);
}
ll g(ll ta){
    ll tmp=C(n-b[ta]-1)-C(n-a[ta+1]-1);
    return qpow(2,ta,tmp);
}
void init_cf(){
    mset(fr);
    mset(uf);
    fr[0]=1;
    uf[0]=1;
    for(ll i=1;i<=n;i++){
        fr[i]=(fr[i-1]*i)%p;
        uf[i]=(uf[i-1]*((k%p+i)%p))%p;
    }
}
void init_ab(){
    mset(a);
    mset(b);
    t=0;
    ll i=0;
    while(1){
        a[t]=i;
        while(S[i]=='0'&&i<n){
            i++;
        }
        b[t]=i;
        while(S[i]=='1'&&i<n){
            i++;
        }
        if(i>=n){
            break;
        }
        t++;
    }
    a[1+t]=n;
}
void init_sg(){
    mset(sg);
    for(ll i=t;i>=0;i--){
        sg[i]=sg[i+1]+g(i);
        sg[i]%=p;
    }
}
void solve(){
    cin>>n>>k>>S;
    init_cf();
    init_ab();
    init_sg();
    ll ans=0;
    for(ll ta=0;ta<=t;ta++){
        ans+=(f(ta)*sg[ta])%p;
        ans%=p;
    }
    cout<<ans<<endl;
}
int main(){
    ll T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

这段代码可以通过样例，时间复杂度 $O(Tn\log p)$ 但 TLE on #2。