#include<bits/stdc++.h>
using namespace std;
const int N=1e6+99,mod=1e9+7;
int n,v[N],ans[N],c[N];
int f[N][2];
char ch[N];
void cal(){
	int l=n+1,r=0;
	for(int i=1;i<=n;i++)
		if(v[i])
			l=min(i,l),r=max(i,r);
	if(r<l){
		for(int i=1;i<=n;i++) ans[i]=0;
		return;
	}
	f[r][1]=3; f[r][0]=0;
	f[r-1][1]=2; f[r-1][0]=1;
	for(int i=r-2;i>=1;i--){
		f[i][0]=1+f[i+1][v[i+1]^1];
		f[i][1]=3+f[i+1][v[i+1]];
	}
	int w=0,ptn=0;
	for(int i=1;i<=r;i++){
		if(i<l) ans[i]=f[i][v[i]];
		else ptn^=v[i],ans[i]=f[i][ptn]+w,w+=2+(ptn==0?2:0);
	}
	for(int i=r+1;i<=n;i++) ans[i]=mod;
	return;
}
void sol(){
	scanf("%d",&n);
	scanf("%s",ch+1);
	for(int i=1;i<=n;i++)
		v[i]=ch[i]-'0';
	cal();
	for(int i=1;i<=n;i++)
		c[i]=ans[i];
	reverse(v+1,v+n+1);
	cal();
	reverse(ans+1,ans+n+1);
	int re=0;
	for(int i=1;i<=n;i++){
		c[i]=min(c[i],ans[i]);
		re=(long long)(re+1ll*i*c[i])%mod;
	}
	printf("%d\n",re);
}
int main(){
	int T; scanf("%d",&T);
	while(T--) sol();
	return 0;
}