#include <bits/stdc++.h>

#define FOR(i, l, r) for (int i = l; i <= (r); ++i)
#define ROF(i, l, r) for (int i = r; i >= (l); --i)
#define rep(n) FOR (_, 1, n)
#define each(i, x) for (auto& i : x)

using namespace std;

using ll = long long;
using db = long double;
using str = string;

#define mp make_pair
#define f first
#define s second

#define ttt template <typename T
ttt > using V = vector<T>;
ttt, size_t n > using A = array<T, n>;

#define sz(x) int((x).size())
#define bg begin
#define all(x) bg(x), end(x)
#define rsz resize
#define pb push_back
#define eb emplace_back

#define il inline
ttt > il bool ckmin(T& x, const T& y) { return y < x ? x = y, true : false; }
ttt > il bool ckmax(T& x, const T& y) { return x < y ? x = y, true : false; }

constexpr int N = 1e6 + 5, mod = 1e9 + 7;
int n;
str s;
A<int, N> a, b, g;
A<A<int, 2>, N> f;
A<A<int, N>, 2> ans;

void proc() {
  cin >> n >> s;
  if (s == str(n, '0')) return void(cout << "0\n");
  FOR (stage, 0, 1) {
    FOR (i, 1, n) a[i] = s[i - 1] - '0';
    int l = n, r = 1;
    ROF (i, 1, n)
      if (a[i]) l = i;
    FOR (i, 1, n)
      if (a[i]) r = i;
    if (l == r) {
      ll h = 0;
      FOR (i, 1, n) h = (h + (ll)i * (i == l ? 3 : 2 * abs(i - l) - 1)) % mod;
      return void(cout << h << "\n");
    }
    f[r - 1] = {1, 2};
    ROF (i, 1, r - 2) {
      f[i][0] = 1 + f[i + 1][a[i + 1] ^ 1];
      f[i][1] = 3 + f[i + 1][a[i + 1]];
    }
    g[l] = 0, b[l] = a[l] ^ 1;
    FOR (i, l + 1, r - 1) {
      if (b[i - 1] == 0)
        b[i] = a[i], g[i] = g[i - 1] + 1;
      else
        b[i] = a[i] ^ 1, g[i] = g[i - 1] + 3;
    }
    FOR (i, 1, l) ans[stage][i] = f[i][a[i]];
    FOR (i, l + 1, r - 1)
      ans[stage][i] = i - l + g[i - 1] +
                      (b[i - 1] == 0 ? 1 + f[i][a[i] ^ 1] : 3 + f[i][a[i]]);
    fill(bg(ans[stage]) + r, bg(ans[stage]) + n + 1, 1e9);
    reverse(all(s));
  }
  ll h = 0;
  FOR (i, 1, n) h = (h + (ll)i * min(ans[0][i], ans[1][n - i + 1])) % mod;
  cout << h << "\n";
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false), cin.exceptions(cin.failbit);
  int t;
  cin >> t;
  rep (t) proc();
}