/*
  ! Though life is hard, I want it to be boiling.
  ! Created: 2024/03/30 09:57:44
*/
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x); i <= (y); i++)
#define pre(i, x, y) for(int i = (x); i >= (y); i--)
inline void JYFILE19();

typedef long long i64;
typedef pair<int, int> PII;

bool ST;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int n, m, ans, a[N], b[N];
int sf1[N], pr1[N], sf2[N], pr2[N];
int sf3[N], pr3[N], sf4[N], pr4[N];
int sf5[N][2], pr5[N][2];
string s;

inline void sol1(int i) {
  if (i == 1) {
    pr5[i - 1][1] = 3;
    pr5[i - 1][0] = 0;
  } else if (i - 1 == pr2[n]) {
    pr5[i - 1][0] = 1;
    pr5[i - 1][1] = 2;
  } else {
    if (a[i - 1] == 1) {
      pr5[i - 1][1] = pr5[i - 2][1] + 3;
      pr5[i - 1][0] = pr5[i - 2][0] + 1;
    } else {
      pr5[i - 1][1] = pr5[i - 2][0] + 3;
      pr5[i - 1][0] = pr5[i - 2][1] + 1;
    }
  }
}
inline void sol2(int i) {
  if (i == n) {
    sf5[i + 1][1] = 3;
    sf5[i + 1][0] = 0;
  } else if (i + 1 == sf2[1]) {
    sf5[i + 1][0] = 1;
    sf5[i + 1][1] = 2;
  } else {
    if (a[i + 1] == 1) {
      sf5[i + 1][1] = sf5[i + 2][1] + 3;
      sf5[i + 1][0] = sf5[i + 2][0] + 1;
    } else {
      sf5[i + 1][1] = sf5[i + 2][0] + 3;
      sf5[i + 1][0] = sf5[i + 2][1] + 1;
    }
  }
}
inline int sol1(int l, int i, int r) {
  int b = a[i] ^ (l != i) ^ pr4[i];
  return (i - l) * 2 + pr3[i] + sf5[i + 1][b];
}
inline int sol2(int l, int i, int r) {
  int b = a[i] ^ (r != i) ^ sf4[i];
  return (r - i) * 2 + sf3[i] + pr5[i - 1][b];
}

inline void solve() {
  cin >> n >> s, ans = 0;
  fro(i, 1, n) a[i] = s[i - 1] - '0';
  fro(i, 1, n) {
    pr1[i] = pr1[i - 1] | a[i];
    pr2[i] = pr2[i - 1];
    if (!pr2[i] && a[i]) pr2[i] = i;
  }
  pre(i, n, 1) {
    sf1[i] = sf1[i + 1] | a[i];
    sf2[i] = sf2[i + 1];
    if (!sf2[i] && a[i]) sf2[i] = i;
  }
  if (pr2[n]) {
    int num = 0;
    fro(i, 1, n) b[i] = a[i];
    fro(i, pr2[n] + 1, n - 1) {
      if (b[i]) pr4[i + 1] = 1;
      if (b[i]) b[i] ^= 1, b[i + 1] ^= 1, num += 2;
      pr3[i + 1] = num;
    }
  }
  if (sf2[1]) {
    int num = 0;
    fro(i, 1, n) b[i] = a[i];
    pre(i, sf2[1] - 1, 1 + 1) {
      if (b[i]) sf4[i - 1] = 1;
      if (b[i]) b[i] ^= 1, b[i - 1] ^= 1, num += 2;
      sf3[i - 1] = num;
    }
  }
  fro(i, 1, n) sol1(i);
  pre(i, n, 1) sol2(i);
  fro(i, 1, n) {
    int f1 = pr2[i - 1], f2 = sf2[i + 1];
    if (f1 && f2) {
      int s1 = sol1(f1, i, f2);
      int s2 = sol2(f1, i, f2);
      ans += min(s1, s2) * i;
    } else if (f2) {
      ans += sol1(i, i, f2) * i;
    } else if (f1) {
      ans += sol2(f1, i, i) * i;
    } else if (a[i]) {
      ans += 3 * i;
    }
    ans %= mod;
  }
  cout << ans << "\n";
  fro(i, 0, n + 1) pr1[i] = sf1[i] = pr2[i] = sf2[i] = 0;
  fro(i, 0, n + 1) pr3[i] = sf3[i] = pr4[i] = sf4[i] = 0;
  fro(i, 0, n + 1) pr5[i][0] = sf5[i][0] = pr5[i][1] = sf5[i][1] = 0;
}

signed main() {
  JYFILE19();
  int t; cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

bool ED;
inline void JYFILE19() {
  srand(random_device{}());
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED-&ST)/1048576.), LIM = 512;
  cerr << "MEMORY: " << MIB << endl, assert(MIB<=LIM);
}