#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5,P=1e9+7;
ll n;
ll d[N],dt[N],c[N];
vector<bool> b;
string s;
bool nx(bool x,bool y){return !(x^y);}
void solve(){
	ll i,l=n+1,r=0;
	for(i=1;i<=n;i++) d[i]=3e18;
	for(i=1;i<=n;i++) if(b[i]) l=min(l,i),r=max(r,i);
	if(!r){for(i=1;i<=n;i++) d[i]=0;return;}
	vector<bool> bs=b;
	for(i=l+1;i<=r;i++) bs[i]=nx(bs[i],bs[i-1]);
	bool t=1,lst;ll cnt[2]={0,0},xx,yy;
	for(i=l;i<=r;i++){
		t=nx(t,b[i]);
		cnt[t]++;
	}lst=t;xx=cnt[0],yy=cnt[1];
	d[l]=cnt[0]*3+cnt[1]-3*(lst==0);
	for(i=l-1;i>=1;i--){
		if(!b[i]) swap(cnt[0],cnt[1]),lst^=1;
		cnt[b[i]]++;
		d[i]=cnt[0]*3+cnt[1]-3*(lst==0);
	}
	cnt[0]=xx,cnt[1]=yy;
	ll c_[2]={0,0};cnt[b[l]]--,c_[b[l]]++;
	bool fl=0;
	t=1;for(i=l;i<=r;i++){
		t=nx(t,b[i]);
	}lst=t;
	for(i=l+1;i<r;i++){
		swap(cnt[0],cnt[1]),lst=!lst;
		fl=!fl;
		d[i]=i-l+(c_[0]+cnt[0])*3+(c_[1]+cnt[1])-3*(lst==0);
		c_[bs[i]^fl]++,cnt[bs[i]^fl]--;
	}
}
void work(){
	ll i;char ch;
	cin>>n;b.resize(n+1);
	for(i=1;i<=n;i++) cin>>ch,b[i]=ch-'0';
	solve();
	for(i=1;i<=n;i++) dt[i]=d[i],d[i]=0;
	reverse(b.begin()+1,b.end());
	solve();
	reverse(d+1,d+n+1);
	for(i=1;i<=n;i++) d[i]=min(d[i],dt[i]);
	d[0]=d[n+1]=3e18;
	for(i=1;i<=n;i++) c[i]=min(d[i-1],d[i+1]);
	ll ans=0;
	for(i=1;i<=n;i++) (ans+=i*c[i])%=P;
	cout<<ans<<'\n';
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int _;cin>>_;while(_--) work();
	// cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
	return 0;
}