#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=1000003;
int n;
bool s[N],par,a[N];
int arr[N],res[N];
int pre[N],suf[N],tmp[N],mn[N];
inline void chmn(int &x,int v){(x>v)&&(x=v);}
void sol(){
	a[0]=0;
	for(int i=1;i<=n;++i) a[i]=s[i]^a[i-1];
	pre[1]=suf[n]=0;
	int pos=1;
	while(pos<=n&&!s[pos]) pre[++pos]=0;
	for(int i=pos;i<n;++i) pre[i+1]=pre[i]+(!a[i])*2+2;
	pos=n;
	while(pos&&!s[pos]) suf[--pos]=0;
	for(int i=pos;i>1;--i) suf[i-1]=suf[i]+(!(a[i-1]^par))*2+2;
	tmp[1]=tmp[2]=0;
	for(int i=1;i+2<=n;++i) tmp[i+2]=tmp[i]+(a[i]!=par)*2+(a[i+1]==par)*2+2;
	mn[n+1]=mn[n+2]=0x3f3f3f3f;
	for(int i=n;i;--i) chmn(mn[i]=suf[i]+tmp[i],mn[i+2]);
	for(int i=1;i+par<=n;++i){
		arr[i]=pre[i]-tmp[i+par]+mn[i+par];
		if(par){
			if(a[i]) arr[i]+=3;
			else arr[i]++;
		}
	}
	if(par) arr[n]=0x3f3f3f3f;
}
void solve(){
	n=read();par=0;
	char cc=getchar();
	while(cc<48||cc>49) cc=getchar();
	for(int i=1;i<=n;++i){s[i]=(cc=='1');par^=s[i];cc=getchar();}
	sol();
	for(int i=1;i<=n;++i) res[i]=arr[i];
	reverse(s+1,s+n+1);
	sol();
	for(int i=1;i<=n;++i) if(res[i]>arr[n-i+1]) res[i]=arr[n-i+1];
	__int128 sum=0;
	for(int i=1;i<=n;++i) sum+=(long long)i*res[i];
	printf("%d\n",int(sum%1000000007));
}
int main(){
	int tc=read();
	while(tc--) solve();
	return 0;
}