#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;

constexpr int N = 1e6 + 9;
constexpr int mod = 1e9 + 7;
int n, a[N], f[N][2], g[N], as[N];
char s[N];

IL void cmin (int &x, const int &y) {
  x > y && (x = y, 0);
}

void slv () {
  cin >> n >> (s + 1);
  if (count(s + 1, s + n + 1, '1') == 0) {
    cout << "0\n";
    return;
  }
  if (count(s + 1, s + n + 1, '1') == 1) {
    int p = find(s + 1, s + n + 1, '1') - s;
    int z = 0;
    L (i, 1, p - 1) {
      z = (z + (LL)i * (2 * (p - i) - 1)) % mod;
    }
    z = (z + 3LL * p) % mod;
    L (i, p + 1, n) {
      z = (z + (LL)i * (2 * (i - p) - 1)) % mod;
    }
    cout << z << '\n';
    return;
  }
  L (i, 1, n) {
    a[i] = s[i] ^ 48;
  }
  memset(as, 0x3f, (n + 1) << 2);
  L (o, 0, 1) {
    int L, R;
    L (i, 1, n) {
      if (a[i]) {
        L = i;
        break;
      }
    }
    R (i, n, 1) {
      if (a[i]) {
        R = i;
        break;
      }
    }
    L (i, R + 1, n + 1) {
      f[i][0] = f[i][1] = 0;
    }
    f[R][0] = a[R] ? 0 : 3;
    f[R][1] = a[R] ? 1 : 2;
    R (i, R - 1, 1) {
      f[i][0] = f[i + 1][a[i] ^ 1];
      f[i][1] = f[i + 1][a[i]] + 2;
    }
    L (i, 0, L) {
      g[i] = 0;
    }
    int C = 0;
    L (i, L + 1, n) {
      C += a[i - 1];
      g[i] = g[i - 1] + (C % 2 ? 0 : 2);
    }
    C = 0;
    L (p, 1, n) {
      C += a[p - 1];
      int l = min(p, L);
      int r = max(p, R);
      cmin(as[o ? n - p + 1 : p], g[p - 1] + (p > L ? f[p][C % 2 == 0] : f[p + 1][a[p]]) + p - l + r - l);
    }
    reverse(a + 1, a + n + 1);
  }
  int z = 0;
  L (i, 1, n) {
    z = (z + (LL)as[i] * i) % mod;
  }
  cout << z << '\n';
}

int main () {
  // FIO("light");
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    slv();
  }
}
// I love WHQ!