#include<bits/stdc++.h>

using namespace std;

#define N 1200000

const int INF=4000000,mod=1e9+7;
int f1[N][2],g1[N][2],f2[N][2],g2[N][2];
int F(int x,int y){
    if (x==0&&y==0) return 0;
    if (x==0&&y==1) return INF;
    if (x==1&&y==0) return INF;
    return 2;
}
int G(int x,int y){
    if (x==0&&y==0) return 0;
    if (x==0&&y==1) return 3;
    if (x==1&&y==0) return 1;
    return 2;
}
void solve(){
    int n; cin>>n;
    string s; cin>>s;
    vector<int> a(n+1);
    for (int i=1;i<=n;++i) a[i]=s[i-1]-'0';
    auto solve=[&](int f[][2],int g[][2]){
        for (int j:{0,1}){
            if (a[1]==j) f[1][j]=0;
            else f[1][j]=INF;
            if (a[1]==j) g[1][j]=0;
            else g[1][j]=INF;
        }
        for (int i=2;i<=n;++i){
            for (int j:{0,1}){
                if (j==a[i]){
                    f[i][j]=f[i-1][0]+4;
                    if (f[i-1][0]==0) f[i][j]=0;
                }
                else{
                    f[i][j]=f[i-1][1]+2;
                }
                if (j==a[i]){
                    g[i][j]=g[i-1][1]+1;
                    if (g[i-1][0]==0) g[i][j]=0;
                }
                else{
                    g[i][j]=min(f[i-1][1]+2,g[i-1][0]+3);
                }
            }
        }
    };
    solve(f1,g1);
    reverse(a.begin()+1,a.begin()+n+1);
    solve(f2,g2);
    reverse(a.begin()+1,a.begin()+n+1);
    long long ans=0;
    for (int i=1;i<=n;++i){
        int tmp=min(f1[i][a[i]]+g2[n-i+1][0],f1[i][!a[i]]+g2[n-i+1][1]);
        tmp=min(tmp,min(f2[n-i+1][a[i]]+g1[i][0],f2[n-i+1][!a[i]]+g1[i][1]));
        (ans+=1ll*tmp*i)%=mod;
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T;
    while (T--) solve();
}