#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[1000005];
int a[1000005];
int ans[2][1000005];
int sm[1000005] , contri[1000005];
int Lmost , Rmost;
int get_even()
{
    for(int i = 0;i <= n;i++) {
        if(s[i] == '0') a[i] = 0;
        else a[i] = 2;
    }
    sm[0] = a[0];
    for(int i = 1;i <= n;i++) sm[i] = (a[i] - sm[i - 1] + 4) % 4;
    int sol = 0;
    for(int i = 0;i <= n - 1;i++) {
      //  printf("CUR %d %d\n",i,sm[i]);
        if(sm[i] == 0) {
            if(i >= Lmost && i < Rmost) sol += (contri[i] = 4);
            else contri[i] = 0;
        }
        else sol += (contri[i] = sm[i]);
    }
    if(sm[n ] == 0) return sol;
    return 1e9;
}
int sol[2][1000005];
int s2[5][1000005];
void cls() {
    for(int i = 0;i <= n;i++) sol[0][i] = sol[1][i] = 0;
    for(int i = 0;i <= n;i++) s2[0][i] = s2[1][i] = s2[2][i] = s2[3][i] = s2[4][i] = 0;
}
int cal_in(int x)
{
    int ans;
    if(s[x] == '0') ans= (3 - a[x] + 4) % 4;
    else ans = (1 - a[x] + 4) % 4;
    if(ans == 3) return -1;
    return ans;
}
int cal_out(int x)
{
    int ans;
    if(s[x] == '0') ans = (1 - a[x] + 4) % 4;
    else ans = (3 - a[x] + 4) % 4;
    if(ans == 3) return -1;
    return ans;
}
void get_odd(int *sans)
{
    int ct = sm[n ];
    for(int ad_od = -2 ; ad_od <= 2;ad_od ++) {
        int cur_ans = 0;
        for(int i = n - 1;i >= 0;i--) {
            int d = sm[i];
            if(i & 1) d += ad_od;
            else d -= ad_od;
            d = (d + 4) % 4;
            if(d == 0) cur_ans += 4;
            else cur_ans += d;

//            cur_ans -= contri[i];

            s2[ad_od + 2][i] = cur_ans ;
          //  printf("s2 %d , %d %d\n",i,ad_od,s2[ad_od + 2][i]);
        }
    }
    for(int t = 0;t < 2;t++) { ///t 1表示奇数位增加1，偶-1 , t 0表示奇数位-1,偶+1
        int x = t * 2 - 1 ;  ///+1 / -1
        int cur_ans = 0;

        sol[t][n + 1] = 1e9;
        for(int i = n ;i >= 0;i--) {
            int delta = x, de = cal_in(i);

            if(i & 1) delta += de;
            else delta -= de;

            int c1 = sm[i];
            if(i & 1) c1 = (c1 + x);
            else c1 = (c1 - x);
            c1 = (c1 + 4) % 4;
            if(c1 == 0) c1 = 4;

            sol[t][i] = sol[t][i + 1] + c1;
            int du = ct;
            if(n & 1) du += delta;
            else du -= delta;
            if((4 + du) % 4 == 0) {
           // printf("ok on %d %d , %d %d\n",i,delta , x , cal_in(i));
                sol[t][i] = min(sol[t][i] , s2[delta + 2][i]);
              //  printf("from i %d , x %d , %d\n",i,x,sol[t][i]);
            }
           // printf("i %d , x %d , %d\n",i,x,sol[t][i]);
        }
    }
    int sum_c = 0;
    for(int i = 0;i <= n;i++) {
        int delta = cal_out(i);
        if(!(i & 1)) delta = -delta;
        //printf("Delta %d %d\n",i,delta);
        sans[i] = sum_c + sol[(delta + 1) / 2][i ];
        sum_c += contri[i];
    }
}
void make_ans(int d)
{
    cls();
    Lmost = 1e9 , Rmost = -1e9;
    for(int i = 0;i < n;i++) {
        if(s[i] == '1') Lmost = min(Lmost , i) , Rmost = max(Rmost , i);
    }
    if(Lmost > Rmost) {
        for(int i = 0;i < n;i++) ans[d][i] = 0;
        return;
    }
    int rn = n;n = Rmost;
    int sol = get_even();
   // cout << "SOL " << sol << '\n';

    get_odd(ans[d]) ;
    for(int i = Lmost;i <= n;i++) ans[d][i] = min(ans[d][i] , sol) ;
    for(int i = n + 1;i < rn;i++) ans[d][i] = 1e9;
    if(Lmost == Rmost) ans[d][Lmost] = 3;
    n = rn ; return;
}
void solve()
{
    const int mod = 1e9 + 7;
    cin >> n;
    cin >> s;
    make_ans(0); //exit(0);
    for(int i = 0;i < n - i - 1;i++) swap(s[i] , s[n - i - 1]);
    make_ans(1);
    int ss = 0;
    for(int i = 0;i < n;i++) {
        int z = min(ans[0][i] , ans[1][n - i - 1]);
       //printf("i %d %d\n",i + 1 , z);
        ss = (ss + 1LL*z*(i + 1)) % mod;
    }
    cout << ss << '\n';
}
int main()
{
  //  freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
    int t;cin >> t;
    while(t--) {
            solve();
    }
    return 0;
}