#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+100,M=1e9+7;
using ll=long long;
using ul=unsigned long long;
using vt=vector<int>;
int T,n,m,L,R,d[N],g[N][2],c[N],ans;
struct dat{int v,k;}f[N];
string s;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z,v;
    for(cin>>T;T--;){
        cin>>n>>s,s='b'+s,ans=0;
        for(i=1,L=0;i<=n;++i)if(s[i]=='1'){L=i;break;}
        if(!L){puts("0");continue;}
        for(R=n;s[R]=='0';--R);
        for(x=1;x<=n;++x)d[x]=M,c[x]=s[x]&1;
        f[L]={0,0};
        for(x=L+1;x<R;++x){
            f[x].v=f[x-1].v+2;
            if(c[x]^f[x-1].k)
                f[x].k=1,f[x].v+=2;
            else f[x].k=0;
        }
        g[R][0]=3,g[R-1][c[R-1]]=1,g[R-1][!c[R-1]]=2;
        for(x=R-2;x>0;--x)
            for(k=0;k<2;++k)
                if(c[x]==k)g[x][k]=g[x+1][1]+1;
                else g[x][k]=g[x+1][0]+3;
        for(x=1;x<=L;++x)d[x]=min(d[x],g[x][0]);
        for(x=L+1;x<R;++x)
            d[x]=min(d[x],f[x-1].v+g[x][!f[x-1].k]+2);
        f[R]={0,0};
        for(x=R-1;x>L;--x){
            f[x].v=f[x+1].v+2;
            if(c[x]^f[x+1].k)
                f[x].k=1,f[x].v+=2;
            else f[x].k=0;
        }
        g[L][0]=3,g[L+1][c[L+1]]=1,g[L+1][!c[L+1]]=2;
        for(x=L+2;x<=n;++x)
            for(k=0;k<2;++k)
                if(c[x]==k)g[x][k]=g[x-1][1]+1;
                else g[x][k]=g[x-1][0]+3;
        for(x=R;x<=n;++x)d[x]=min(d[x],g[x][0]);
        for(x=L+1;x<R;++x)
            d[x]=min(d[x],f[x+1].v+g[x][!f[x+1].k]+2);
        for(x=1;x<=n;++x)ans=(1ll*x*d[x]+ans)%M;
        printf("%d\n",ans);
    }
    return 0;
}