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

typedef long long ll;

const ll mod = 1e9 + 7;

ll T, n, ans;
ll a[1000100];
ll b[1000100];
ll d[1000100];
ll f[1000100][4];
ll g[1000100][4];
ll p[1000100];
ll q[1000100];
char c[1000100];

inline void work1() {
	f[1][0] = 0;
	f[1][1] = 3;
	for (ll i = 2; i <= n; i++) {
		if (!f[i - 1][0]) {
			if (!a[i - 1]) {
				f[i][0] = 0;
				f[i][1] = 3;
			} else {
				f[i][0] = 1;
				f[i][1] = 2;
			}
		} else {
			if (!a[i - 1]) {
				f[i][0] = f[i - 1][1] + 1;
				f[i][1] = 3 + f[i - 1][0];
			} else {
				f[i][0] = f[i - 1][0] + 1;
				f[i][1] = 3 + f[i - 1][1];
			}
		}
	}
	g[n][0] = 0;
	g[n][1] = 3;
	for (ll i = n - 1; i >= 1; i--) {
		if (!g[i + 1][0]) {
			if (!a[i + 1]) {
				g[i][0] = 0;
				g[i][1] = 3;
			} else {
				g[i][0] = 1;
				g[i][1] = 2;
			}
		} else {
			if (!a[i + 1]) {
				g[i][0] = g[i + 1][1] + 1;
				g[i][1] = 3 + g[i + 1][0];
			} else {
				g[i][0] = g[i + 1][0] + 1;
				g[i][1] = 3 + g[i + 1][1];
			}
		}
	}
	return;
}

int main() {
//	freopen("light.in", "r", stdin);
//	freopen("light.out", "w", stdout);
	scanf("%lld", &T);
	while (T--) {
		ans = 0;
		scanf("%lld", &n);
		scanf("%s", c + 1);
		for (ll i = 1; i <= n; i++) {
			a[i] = c[i] - '0';
			b[i] = d[i] = a[i];
		}
		work1();
		p[1] = 0;
		for (ll i = 2; i <= n; i++) {
			if (!a[i - 1] && !p[i - 1]) {
				p[i] = 0;
				continue;
			}
			p[i] = p[i - 1] + 2;
			if (!b[i - 1]) {
				p[i] += 2;
				b[i] = a[i];
			} else {
				b[i] = (a[i] ^ 1);
			}
		}
		q[n] = 0;
		for (ll i = n - 1; i >= 1; i--) {
			if (!a[i + 1] && !q[i + 1]) {
				q[i] = 0;
				continue;
			}
			q[i] = q[i + 1] + 2;
			if (!d[i + 1]) {
				q[i] += 2;
				d[i] = a[i];
			} else {
				d[i] = (a[i] ^ 1);
			}
		}
		for (ll i = 1; i <= n; i++) {
			ans += i * min(p[i] + g[i][b[i]], q[i] + f[i][d[i]]);
			ans %= mod;
		}
		printf("%lld\n", ans);
		for (ll i = 1; i <= n; i++) {
			f[i][0] = g[i][0] = 0;
			f[i][1] = g[i][1] = 0;
			p[i] = q[i] = 0;
		}
	}
	return 0;
}