#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 1000010;
const int mod = 1000000007;

inline void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
inline int Add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
inline int Sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; }

int n, a[maxn], b[maxn], f[maxn], g[maxn], c[maxn], cnt0[maxn], cnt1[maxn];
char s[maxn];

void calc(int *ans) {
  rep (i, 1, n) b[i] = a[i], ans[i] = 1e9;
  int s = n + 1, t = 0;
  rep (i, 1, n) if (b[i]) chkmn(s, i), chkmx(t, i);
  c[s - 1] = 0;
  rep (i, s, t) c[i] = c[i - 1] ^ (!b[i]);
  cnt0[s - 1] = cnt1[s - 1] = 0;
  rep (i, s, t) cnt0[i] = cnt0[i - 1] + ((c[i - 1] ^ b[i]) == 0);
  rep (i, s, t) cnt1[i] = cnt1[i - 1] + ((c[i - 1] ^ b[i]) == 1);
  rep (i, 1, s - 1) {
    int ps = s - i;
    ans[i] = ps + ps / 2 * 2;
    if (ps & 1) ans[i] += 3 * cnt0[t - 1] + cnt1[t - 1];
    else ans[i] += 3 * cnt1[t - 1] + cnt0[t - 1];
    if ((ps & 1) ^ c[t - 1] ^ b[t]) ans[i]--;
  }
  int r0 = cnt0[t - 1], r1 = cnt1[t - 1], s0 = 0, s1 = 0, sum = 0, lz = 0;
  rep (i, s, t - 1) sum ^= (!b[i]);
  rep (i, s, t - 1) {
    ans[i] = 3 * (r1 + s1) + r0 + s0 + i - s;
    if (b[t] ^ c[t - 1] ^ lz) ans[i]--;
    if ((b[i] ^ c[i - 1] ^ lz)) r1--, s0++;
    else r0--, s1++;
    swap(r0, r1), lz ^= 1;
  }
  if (s == t) ans[s] = 3;
}

void work() {
  cin >> n >> s;
  rep (i, 1, n) a[i] = s[i - 1] - '0';
  int s1 = 0;
  rep (i, 1, n) s1 += a[i];
  if (!s1) return cout << "0\n", void();
  calc(f), reverse(a + 1, a + n + 1), calc(g);
  int sum = 0;
  rep (i, 1, n) add(sum, 1ll * i * min(f[i], g[n - i + 1]) % mod);
  cout << sum << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}