#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
int read() {
	int x=0; char ch=getchar(); 
	while (!isdigit(ch)) ch=getchar(); 
	while (isdigit(ch)) x=x*10+ch-48, ch=getchar(); 
	return x; 
}

const int N=1e6+5, mod=1e9+7;
char s[N];
int a[N], n, L, R, cc;

ll C(int x) {
	int cnt=0, res=0;
	for (int i=1; i<=n; i++) cnt+=a[i];
	if (cnt&1) res++, a[x]^=1;
	for (int i=1, l=0; i<=n; i++) if (a[i]) {
		if (l) res+=2*(i-l), l=0;
		else l=i;
	}
	if (cnt&1) a[x]^=1;
	return res;
}
int rev(int l, int r) {
	for (int i=l; i<=r; i++) a[i]^=1;
	if ((r-l)&1) return cc;
	return cc^1;
}
int ask(int x) {
	int res=1;
	for (int i=1; i<=x; i++) res^=a[i];
	return res;
}
int Match() {
	int res=0;
	for (int i=1, l=0; i<=n; i++) if (a[i]) {
		if (l) res+=2*(i-l), l=0;// )
		else l=i;// (
	}
	return res;
}
ll res;
void New(const int x, const int y, int &las) {
	if (!a[x]&&!a[y]) {
//		cout<<"gua\n";
		if (las) res+=2;
		else res-=2;
	}  else if (!a[x]&&a[y]) {
		if (las) res+=2;
		else res-=2;
		las^=1;
	} else if (a[x]&&!a[y]) {
		if (las) res-=2;
		else res+=2;
		las^=1;
	} else {
		if (las) res-=2;
		else res+=2;
	}
}
ll t[N];
void solve() {
	n=read(), L=n, R=-1, cc=0;
	scanf("%s", s+1);
	for (int i=1; i<=n; i++) a[i]=s[i]&1;
	for (int i=1; i<=n; i++) if (a[i]) R=i, cc++;
	if (R==-1) return puts("0"), void();
	for (int i=n; i>=1; i--) if (a[i]) L=i;
	ll ans=0; cc&=1;
	int o=rev(2, R); res=0;
	if (o) a[R-1]^=1, res++;
	res+=Match();
	for (int i=1, las=1; i<L; i+=2) {
		ans=(ans+(res+R-i)*i)%mod;
		New(i+1, i+2, las);
	}
	rev(2, R);
	if (o) a[R-1]^=1;
	o=rev(3, R); res=0;
	if (o) a[R-1]^=1, res++;
	res+=Match();
	for (int i=2, las=ask(2); i<L; i+=2) {
		ans=(ans+(res+R-i)*i)%mod;
		New(i+1, i+2, las);
	}
	rev(3, R);
	if (o) a[R-1]^=1;
	o=rev(L, R), res=0;
	if (o) a[L+1]^=1, res++;
	res+=Match();
	for (int i=R+1, las=ask(R+1); i<=n; i+=2) {
		ans=(ans+(res+i-L)*i)%mod;
		New(i+1, i+2, las);
	}
	o=rev(L, R);
	if (o) a[L+1]^=1;
	o=rev(L, R+1), res=0;
	if (o) a[L+1]^=1, res++;
	res+=Match();
	for (int i=R+2, las=ask(R+2); i<=n; i+=2) {
		ans=(ans+(res+i-L)*i)%mod;
		New(i+1, i+2, las);
	}
	o=rev(L, R+1);
	if (o) a[L+1]^=1;
	if (L==R) return printf("%lld\n", ans+3*L), void();
	a[L]^=1, cc^=1;
	o=rev(L, R); res=0;
	if (o) a[R-1]^=1, res++;
	res+=Match();
	for (int i=L, las=ask(L-1); i<=R; i+=2) {
		t[i]=res+R-i+2*(i-L);
		New(i, i+1, las);
	}
	rev(L, R);
	if (o) a[R-1]^=1;
	o=rev(L+1, R), res=0;
	if (o) a[R-1]^=1, res++;
	res+=Match();
	for (int i=L+1, las=ask(L); i<=R; i+=2) {
		t[i]=res+R-i+2*(i-L);
		New(i, i+1, las);
	}
	rev(L+1, R);
	if (o) a[R-1]^=1;
	a[L]^=1;
	a[R]^=1;
	o=rev(L, L), res=0;
	if (o) a[L+1]^=1, res++;
	res+=Match();
	for (int i=L, las=ask(L); i<=R; i+=2) {
		t[i]=min(t[i], res+i-L+2*(R-i));
		New(i+1, i+2, las);
	}
	rev(L, L);
	if (o) a[L+1]^=1;
	o=rev(L, L+1), res=0;
	if (o) a[L+1]^=1, res++;
	res+=Match();
	for (int i=L+1, las=ask(L+1); i<=R; i+=2) {
		t[i]=min(t[i], res+i-L+2*(R-i));
		New(i+1, i+2, las);
	}
	rev(L, L+1);
	if (o) a[L+1]^=1;
	a[R]^=1, cc^=1;
	for (int i=L; i<=R; i++) 
		ans=(ans+t[i]*i)%mod;
	printf("%lld\n", ans%mod);
}

int main() {
	int T=read();
	while (T--) solve();
    return 0; 
}