#include <algorithm>
#include <cstdio>

constexpr int MAXN = 1000000 + 2;
constexpr int P = 1000000007;

int pre[MAXN][2], suf[MAXN][2];
int pre_rev[MAXN][2], suf_rev[MAXN][2];
int sum[MAXN];

char s[MAXN];

inline void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}

void solve() {
    int n, L, R, ans = 0;
    scanf("%d%s", &n, s + 1);

    for (L = 1; L <= n && s[L] == '0'; L ++);
    for (R = n; R && s[R] == '0'; R --);

    if (!R) {
        puts("0");
        return;
    }

    if (L == R) {
        for (int i = 1; i <= n; i ++) {
            if (i == L) {
                add(ans, 3 * L);
            } else {
                add(ans, ((abs(L - i) << 1) - 1ll) * i % P);
            }
        }

        printf("%d\n", ans);
        return;
    }

    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + (s[i] ^ '0');
    }

    bool fl, tag;

    for (int i = 0; i < 2; i ++) {
        pre[L][i] = pre_rev[L][i] = 0;
    }
    for (int i = L + 1; i <= n; i ++) {
        fl = s[i] ^ '0' ^ 1;
        for (int j = 0; j < 2; j ++) {
            pre[i][j] = pre[i - 1][j ^ fl] + (j == fl);
            pre_rev[i][j] = pre_rev[i - 1][j];
        }
        pre_rev[i][(sum[i] - sum[L]) & 1] ++;
    }

    for (int i = 0; i < 2; i ++) {
        suf[R][i] = suf_rev[R][i] = 0;
    }
    for (int i = R - 1; i; i --) {
        fl = s[i] ^ '0' ^ 1;
        for (int j = 0; j < 2; j ++) {
            suf[i][j] = suf[i + 1][j ^ fl] + (j == fl);
            suf_rev[i][j] = suf_rev[i + 1][j];
        }
        suf_rev[i][(sum[R - 1] - sum[i - 1]) & 1] ++;
    }

    for (int i = 1; i < L; i ++) {
        tag = (R ^ i ^ sum[R] ^ sum[i] ^ 1) & 1;
        add(ans, i * (suf[i + 1][0] + 3ll * suf[i + 1][1] + tag) % P);
    }
    for (int i = R + 1; i <= n; i ++) {
        tag = (i ^ L ^ sum[i - 1] ^ sum[L]) & 1;
        add(ans, i * (pre[i - 1][0] + 3ll * pre[i - 1][1] + tag) % P);
    }

    if (L + 1 == R) {
        add(ans, (L + R) << 1);
        printf("%d\n", ans);
        return;
    }

    for (int i = L + 1; i < R; i ++) {
        fl = (sum[i - 1] ^ sum[L]) & 1;
        tag = (R ^ i ^ sum[R] ^ sum[i - 1] ^ fl) & 1;
        int cost = i - L + pre_rev[i - 1][0] + suf[i][fl] + tag
                     + 3 * (pre_rev[i - 1][1] + suf[i][fl ^ 1]);

        fl = (sum[R - 1] ^ sum[i]) & 1;
        tag = (i ^ L ^ sum[i] ^ sum[L] ^ fl ^ 1) & 1;
        cost = std::min(cost, R - i + suf_rev[i + 1][0] + tag
             + pre[i][fl] + 3 * (suf_rev[i + 1][1] + pre[i][fl ^ 1]));

        add(ans, (long long){i} * cost % P);
    }

    fl = s[L + 1] & 1;
    tag = (R ^ L ^ sum[R] ^ sum[L + 1] ^ fl) & 1;
    add(ans, L * (2ll + pre_rev[L + 1][0] + suf[L + 2][fl] + tag
               + 3 * (pre_rev[L + 1][1] + suf[L + 2][fl ^ 1])));

    fl = s[R - 1] & 1;
    tag = (R ^ L ^ sum[R - 2] ^ sum[L] ^ fl ^ 1) & 1;
    add(ans, R * (2ll + suf_rev[R - 1][0] + pre[R - 2][fl] + tag
               + 3 * (suf_rev[R - 1][1] + pre[R - 2][fl ^ 1])) % P);

    printf("%d\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);

    while (T --) {
        solve();
    }

    return 0;
}