#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
	typedef long long ll;
	typedef pair<int,int> pii;
	il int read(){
		int x=0,f=1;char c=gc();
		while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
		while(c>='0'&&c<='9')x=x*10+c-48,c=gc();
		return x*f;
	}
	il void write(int x){
		char buf[23];int len=0;
		if(x<0)pc('-'),x=-x;
		do buf[++len]=x%10,x/=10;while(x);
		while(len)pc(buf[len--]+'0');
	}
}
using namespace my_std;
const int N=1e6+7,M=-1,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,a[N],b[N],f[N][2][2],g[N][2][2],s[N][2][2],t[N][2][2];
char str[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void Yorushika(){
	scanf("%d%s",&n,str+1);
	rep(i,1,n){
		a[i]=str[i]-'0',b[i]=1-a[i];
	}
	mems(s,0x3f),mems(t,0x3f);
	f[1][0][0]=0,f[1][0][1]=1;
	s[1][0][0]=0,s[1][0][1]=0;
	rep(i,2,n){
		f[i][0][0]=f[i-1][0][a[i-1]^1],f[i][0][1]=f[i-1][0][a[i-1]];
		s[i][0][0]=s[i-1][0][a[i-1]^1]+1,s[i][0][1]=s[i-1][0][a[i-1]]+3;
	}
	g[n][0][0]=0,g[n][0][1]=1;
	t[n][0][0]=0,t[n][0][1]=0;
	drep(i,n-1,1){
		g[i][0][0]=g[i+1][0][a[i+1]^1],g[i][0][1]=g[i+1][0][a[i+1]];
		t[i][0][0]=t[i+1][0][a[i+1]^1]+1,t[i][0][1]=t[i+1][0][a[i+1]]+3;
	}
	f[1][1][0]=0,f[1][1][1]=1;
	s[1][1][0]=0,s[1][1][1]=0;
	rep(i,2,n){
		f[i][1][0]=f[i-1][1][b[i-1]^1],f[i][1][1]=f[i-1][1][b[i-1]];
		s[i][1][0]=s[i-1][1][b[i-1]^1]+1,s[i][1][1]=s[i-1][1][b[i-1]]+3;
	}
	g[n][1][0]=0,g[n][1][1]=1;
	t[n][1][0]=0,t[n][1][1]=0;
	drep(i,n-1,1){
		g[i][1][0]=g[i+1][1][b[i+1]^1],g[i][1][1]=g[i+1][1][b[i+1]];
		t[i][1][0]=t[i+1][1][b[i+1]^1]+1,t[i][1][1]=t[i+1][1][b[i+1]]+3;
	}
	int p=1,q=n;
	while(p<=n&&!a[p]){
		p++;
	}
	while(p>=1&&!a[q]){
		q--;
	}
	if(p>n){
		puts("0");
		return;
	}
	int res=0;
	rep(i,1,n){
		int l=min(p,i),r=max(q,i);
		int x=0,y=0,sum=r-i,ans=inf;
		if(r==i){
			y=a[r];
		}else{
			y=a[r]^1;
		}
		if(r==i){
			if(f[r][0][y]==f[l][0][0]){
				sum+=s[r][0][y]-s[l][0][0];
			}else{
				sum+=s[r][0][y]-s[l][0][1]-1;
			}
		}else{
			if(f[r][1][y]==f[i][1][0]){
				x=0;
			}else{
				x=1;
			}
			sum+=s[r][1][y]-s[i][1][x],x^=1;
			if(l==1){
				sum+=s[i][0][x]-f[i][0][x];
			}else{
				if(f[i][0][x]==f[l][0][0]){
					sum+=s[i][0][x]-s[l][0][0];
				}else{
					sum+=s[i][0][x]-s[l][0][1]-1;
				}
			}
		}
		ans=min(ans,sum);
		
		sum=i-l;
		if(l==i){
			y=a[l];
		}else{
			y=a[l]^1;
		}
		if(l==i){
			if(g[l][0][y]==g[r][0][0]){
				sum+=t[l][0][y]-t[r][0][0];
			}else{
				sum+=t[l][0][y]-t[r][0][1]-1;
			}
		}else{
			if(g[l][1][y]==g[i][1][0]){
				x=0;
			}else{
				x=1;
			}
			sum+=t[l][1][y]-t[i][1][x],x^=1;
			if(r==n){
				sum+=t[i][0][x]-g[i][0][x];
			}else{
				if(g[i][0][x]==g[r][0][0]){
					sum+=t[i][0][x]-t[r][0][0];
				}else{
					sum+=t[i][0][x]-t[r][0][1]-1;
				}
			}
		}
		ans=min(ans,sum);
		// printf("**%d %d\n",ans,sum);
		res=Mod(res,1ll*ans*i%mod);
	}
	printf("%d\n",res);
}
signed main(){
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}