#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;
const ll mod = 1000000007;

int n, a[maxn], b[maxn], tag[maxn];
ll f[maxn], g[maxn];
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	for (int i = 0; i <= n + 1; ++i) {
		tag[i] = 0;
		f[i] = g[i] = 1e18;
	}
	bool fl = 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = s[i] - '0';
		fl &= (!a[i]);
	}
	if (fl) {
		puts("0");
		return;
	}
	vector<int> S;
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			S.pb(i);
		}
		b[i] = a[i];
		if (i > 1) {
			b[i] ^= (b[i - 1] ^ 1);
		}
	}
	int c0 = 0, c1 = 0;
	for (int i = 1; i <= S.back(); ++i) {
		c0 += (b[i] == 0);
		c1 += (b[i] == 1);
	}
	for (int i = 1; i <= S[0]; ++i) {
		f[i] = c0 + c1 * 3;
		tag[i] ^= tag[i - 1];
		if (i + 1 <= S.back() && (b[S.back()] ^ tag[i]) && (b[S.back() - 1] ^ tag[i])) {
			f[i] -= 4;
		}
		if (!(b[S.back()] ^ tag[i])) {
			--f[i];
		}
		// printf("%d %d %d %lld\n", i, c0, c1, f[i]);
		c0 -= ((b[i] ^ tag[i]) == 0);
		c1 -= ((b[i] ^ tag[i]) == 1);
		tag[i] ^= 1;
		swap(c0, c1);
	}
	for (int i = 0; i <= n + 1; ++i) {
		tag[i] = 0;
	}
	c0 = c1 = 0;
	int s0 = 0, s1 = 0;
	for (int i = S[0]; i <= S.back(); ++i) {
		b[i] = a[i];
		if (i > S[0]) {
			b[i] ^= (b[i - 1] ^ 1);
		} else {
			b[i] ^= 1;
		}
		if (i > S[0]) {
			c0 += (b[i] == 0);
			c1 += (b[i] == 1);
		} else {
			s0 += (b[i] == 0);
			s1 += (b[i] == 1);
		}
	}
	for (int i = S[0] + 1; i < S.back(); ++i) {
		tag[i] ^= tag[i - 1];
		f[i] = (c0 + s0) + (c1 + s1) * 3 + i - S[0];
		if ((b[S.back()] ^ tag[i]) && (b[S.back() - 1] ^ tag[i])) {
			f[i] -= 4;
		}
		if (!(b[S.back()] ^ tag[i])) {
			--f[i];
		}
		// printf("%d %d %d %d %d %lld\n", i, c0, s0, c1, s1, f[i]);
		c0 -= ((b[i] ^ tag[i]) == 0);
		c1 -= ((b[i] ^ tag[i]) == 1);
		tag[i] ^= 1;
		swap(c0, c1);
		s0 += ((b[i] ^ tag[i]) == 0);
		s1 += ((b[i] ^ tag[i]) == 1);
	}
	vector<int>().swap(S);
	for (int i = 0; i <= n + 1; ++i) {
		tag[i] = 0;
	}
	reverse(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			S.pb(i);
		}
		b[i] = a[i];
		if (i > 1) {
			b[i] ^= (b[i - 1] ^ 1);
		}
	}
	c0 = c1 = 0;
	for (int i = 1; i <= S.back(); ++i) {
		c0 += (b[i] == 0);
		c1 += (b[i] == 1);
	}
	for (int i = 1; i <= S[0]; ++i) {
		g[i] = c0 + c1 * 3;
		tag[i] ^= tag[i - 1];
		if (i + 1 <= S.back() && (b[S.back()] ^ tag[i]) && (b[S.back() - 1] ^ tag[i])) {
			g[i] -= 4;
		}
		if (!(b[S.back()] ^ tag[i])) {
			--g[i];
		}
		c0 -= ((b[i] ^ tag[i]) == 0);
		c1 -= ((b[i] ^ tag[i]) == 1);
		tag[i] ^= 1;
		swap(c0, c1);
	}
	for (int i = 0; i <= n + 1; ++i) {
		tag[i] = 0;
	}
	c0 = c1 = s0 = s1 = 0;
	for (int i = S[0]; i <= S.back(); ++i) {
		b[i] = a[i];
		if (i > S[0]) {
			b[i] ^= (b[i - 1] ^ 1);
		} else {
			b[i] ^= 1;
		}
		if (i > S[0]) {
			c0 += (b[i] == 0);
			c1 += (b[i] == 1);
		} else {
			s0 += (b[i] == 0);
			s1 += (b[i] == 1);
		}
	}
	for (int i = S[0] + 1; i < S.back(); ++i) {
		tag[i] ^= tag[i - 1];
		g[i] = (c0 + s0) + (c1 + s1) * 3 + i - S[0];
		if ((b[S.back()] ^ tag[i]) && (b[S.back() - 1] ^ tag[i])) {
			g[i] -= 4;
		}
		if (!(b[S.back()] ^ tag[i])) {
			--g[i];
		}
		c0 -= ((b[i] ^ tag[i]) == 0);
		c1 -= ((b[i] ^ tag[i]) == 1);
		tag[i] ^= 1;
		swap(c0, c1);
		s0 += ((b[i] ^ tag[i]) == 0);
		s1 += ((b[i] ^ tag[i]) == 1);
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		f[i] = min(f[i], g[n - i + 1]);
		ans = (ans + f[i] * i) % mod;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}