#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
using namespace std;
const int N=1e6+10,M=1e6+10,mod=1e9+7;
inline void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
const int Inf=1e9;
int f[N][2],a[N],n;
void calc(int *ans){
	int B=0,E=0;
	for(int i=1;i<=n;i++) if(a[i]){
		if(!B) B=i;E=i;
	}
	f[E][1]=2,f[E][0]=1;
	for(int i=E-1;i;i--) for(int j=0;j<2;j++){
		f[i][j]=f[i+1][j^a[i]^1]+2*j+1;
	}
	for(int i=1,w=0,lst=0;i<E;i++){
		if(i<=B) ans[i]=f[i+1][a[i]];
		else ans[i]=(i-B)+w+f[i][lst],w+=(lst?3:1),lst^=a[i];
	}
	for(int i=E;i<=n;i++) ans[i]=Inf;
	if(B==E) ans[E]=3;
}
int ans[2][N];
char s[N];
void solve(){
	cin>>n>>(s+1);
	int Ans=0;
	for(int i=1;i<=n;i++) a[i]=s[i]=='1';
	bool flag=0;for(int i=1;i<=n;i++) flag|=a[i];
	if(!flag) return cout<<0<<'\n',void();
	calc(ans[0]);reverse(a+1,a+n+1);calc(ans[1]);
	for(int i=1;i<=n;i++) Add(Ans,1ll*min(ans[0][i],ans[1][n-i+1])*i%mod);
	cout<<Ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}