#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(ll k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
策略很简单,走到最边上在走回去
dp维护不取反的一边,另一边动态维护
但是大模拟
*/
const ll mod=1e9+7;
int t,n;
ll ans[1000005],dp[1000005][2];
char s[1000005];
void solve(){
	int l=0,r=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='1'){
			l=i;
			break;
		}
	}
	for(int i=n;i;i--){
		if(s[i]=='1'){
			r=i;
			break;
		}
	}
	dp[r-1][1]=2;
	dp[r-1][0]=1;
	for(int i=r-2;i>0;i--){
		dp[i][0]=dp[i+1][!(s[i+1]-'0')]+1;
		dp[i][1]=dp[i+1][s[i+1]-'0']+3;
	}
	for(int i=1,now=0,f=0;i<r;i++){
		if(i<l)
			ans[i]=min(dp[i][s[i]-'0'],ans[i]);
		else{
			ans[i]=min(ans[i],dp[i][f^(s[i]-'0')]+now);
			if((s[i]=='1')^f){
				f=1;
				now++;
			}
			else{
				now+=3;
				f=0;
			}
			now++;
		}
	}
}
int main(){
	t=read();
	while(t--){
		n=read();
		scanf("%s",s+1);
		int flag=0,num=0;
		for(int i=1;i<=n;i++){
			ans[i]=1e9;
			if(s[i]=='1')
				flag=1,num++;
		}
		if(!flag){
			puts("0");
			continue;
		}
		if(num==1){
			int id=0;
			for(int i=1;i<=n;i++){
				if(s[i]=='1')
					id=i;
			}
			ans[id]=3;
		}
		solve();
		reverse(s+1,s+n+1);
		reverse(ans+1,ans+n+1);
		solve();
		reverse(ans+1,ans+n+1);
		ll sum=0;
		for(int i=1;i<=n;i++){
			sum+=ans[i]*i%mod;
			sum%=mod;
		}
		work(sum);
		putchar('\n');
	}
	return 0;
}