#include <bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int N = 1e6 + 10;
int n;
char s[N];
int f[N][2];
inline void Solve(int ans[N]) {
    static int a[N];
    for (int i = 1; i <= n; ++i) a[i] = (s[i] == '1');
    int bp = 0, ep;
    for (int i = 1; i <= n; ++i) if (a[i]) {
        if (!bp) bp = i;
        ep = i;
    }
    f[ep][1] = 2;
    f[ep][0] = 1;
    for (int i = ep - 1; i; --i) {
        for (int j = 0; j < 2; ++j) {
            f[i][j] = f[i + 1][j ^ a[i] ^ 1] + 2 * j + 1;
        }
    }
    for (int i = 1, cost = 0, last = 0; i < ep; ++i) 
        if (i <= bp) {
            ans[i] = f[i + 1][a[i]];
        } else {
            ans[i] = (i - bp) + cost + f[i][last];
            cost += (last == 1 ? 3 : 1);
            last ^= 1 ^ !a[i];
        }
    for (int i = ep; i <= n; ++i) ans[i] = 1e9;
    if (bp == ep) ans[ep] = 3;
    // printf("%s\n", s + 1);
    // for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    // puts("");
}
int ans[2][N];
int main() {
    int Case;
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d%s", &n, s + 1);
        if (find(s + 1, s + n + 1, '1') == s + n + 1) {
            puts("0");
            continue;
        }
        for (int round = 0; round < 2; ++round) {
            Solve(ans[round]);
            reverse(s + 1, s + n + 1);
        }
        int rst = 0;
        for (int i = 1; i <= n; ++i) {
            rst = (rst + 1ll * i * min(ans[0][i], ans[1][n - i + 1])) % p;
        }
        printf("%d\n", rst);
    }
    return 0;
}