//tomorin
#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define MOD 1000000007
#define P(x) px[x]
#define Q(x) (px[x]^((x)&1))
#define S(x) (px[(x)-1]^px[n])
#define len (rr-ll+1)
#define cntP (sp[rr]-sp[ll-1])
#define cntQ (sq[rr]-sq[ll-1])
#define cc(ll,rr,P,c1,v) if(ll<=rr){if(P(x-v)^nw)c1+=(len-cnt##P)*2;else c1+=cnt##P*2;nw=P(v?ll:rr)^P(x-v)^nw,x=v?(ll+1):rr;}
using namespace std;
int T,n,L,R;string s;
bool a[N],px[N];
signed sp[N],sq[N];
int calc(int st){
	int l=L,r=R,c1,c2,x,nw,ll,rr;
	if(st==1&&r==1||st==n&&l==n)return 3;
	if(st<l)l=st+1;
	if(st>r)r=st-1;
	x=st,c1=0;
	x=max(st,r),nw=a[x]^(x>st),c1=max(r-st,0ll)+x-l-1+nw*2;
	// i in [max(l,st),x-2],?cnt:P(i)^P(x-1)^nw
	ll=max(l,st),rr=x-2;cc(ll,rr,P,c1,1)
	// while(x>max(l+1,st+1))--x,nw=nw^a[x],c1+=nw*2;
	// cout<<nw<<' '<<x<<'\n';
	// i in [l,x-2],?cnt:Q(i)^Q(x-1)^nw
	ll=l,rr=x-2;cc(ll,rr,Q,c1,1)
	while(x>l+1)--x,nw=nw^a[x]^1,c1+=nw*2;//max(l,st)+1->l+1
	c1+=(nw^a[l]^(l>st));
	x=min(st,l),nw=a[x]^(x<st),c2=max(st-l,0ll)+r-1-x+nw*2;
	// i in [x+1,min(r,st)-1],?cnt:P(x)^P(i)^nw
	ll=x+1,rr=min(r,st)-1;cc(ll,rr,P,c2,0)
	// if(ll<=rr){if(P(x)^nw)c2+=(len-cntP)*2;else c2+=cntP*2;nw=P(rr)^P(x)^nw,x=rr;}
	// while(x<min(r-1,st-1))++x,nw=nw^a[x],c2+=nw*2;
	// i in [x+1,r-1],?cnt:Q(x)^Q(i)^nw
	ll=x+1,rr=r-1;cc(ll,rr,Q,c2,0)
	// while(x<r-1)++x,nw=nw^a[x]^1,c2+=nw*2;
	c2+=(nw^a[r]^(r<st));
	// clog<<c1<<' '<<c2<<'\n';
	return min(c1,c2);
}
void solve(){
	cin>>n>>s;int ans=L=R=0;
	for(int i=1;i<=n;i++){
		a[i]=(s[i-1]=='1');
		if(a[i]&&!L)L=i;
		if(a[i])R=i;
	}
	for(int i=1;i<=n;i++)
		px[i]=px[i-1]^a[i],
		sp[i]=sp[i-1]+P(i),
		sq[i]=sq[i-1]+Q(i);
	if(L)for(int i=1;i<=n;i++)
		ans=(ans+calc(i)*i)%MOD;
	cout<<ans<<'\n';
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	while(T--)solve();
	return 0;
}