#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int maxn=1e6+5;
int ans[maxn],f[maxn][2],g[maxn],a[maxn],n;
char s[maxn];
inline void calc(){
    int l=n+1,r=0;
    for(int i=1;i<=n;i++) if(a[i]) l=min(l,i),r=max(r,i);
    if(l>r){for(int i=1;i<=n;i++) ans[i]=0; return ;}
    f[r][0]=0,f[r][1]=3;
    f[r-1][0]=1,f[r-1][1]=2;
    for(int i=r-2;i>=1;i--){
        f[i][0]=f[i+1][a[i+1]^1]+1;
        f[i][1]=f[i+1][a[i+1]]+3;
    }
    int p=0,w=0;
    for(int i=1;i<=r;i++){
        if(i<l) ans[i]=f[i][a[i]];
        else p^=a[i],ans[i]=f[i][p]+w,w+=2+(p?0:2);
    }
    for(int i=r+1;i<=n;i++) ans[i]=1919810;
}
inline void solve(){
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'0';
    calc();
    for(int i=1;i<=n;i++) g[i]=ans[i];
    reverse(a+1,a+n+1);
    calc();
    reverse(ans+1,ans+n+1);
    ll ret=0;
    for(int i=1;i<=n;i++){
        g[i]=min(g[i],ans[i]);
        ret=(ret+(ll)i*g[i])%mod;
    }
    printf("%lld\n",ret);
}
int main(){
    int T; scanf("%d",&T);
    while(T--) solve();
    return 0;
}