//Shirasu Azusa 2024.03
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
int n,s[N],f[2][N][2],g[2][N][2],ans[N];
char c[N];

void dp1(int f[N][2],int st) {
  f[st][0]=0;
  rep(i,st,n-1) {
    if(s[i]==1) {
      chmin(f[i+1][1],f[i][1]+1);
      chmin(f[i+1][0],f[i][0]+3);
    } else {
      chmin(f[i+1][1],f[i][0]+1);
      chmin(f[i+1][0],f[i][1]+3);
    }
  }
}
void dp2(int f[N][2],int st) { //s[st]=1;
  f[st][1]=0; if(st!=1) f[st][0]=3;
  f[st+1][s[st+1]^1]=2, f[st+1][s[st+1]]=1;
  rep(i,st+2,n) {
    if(s[i]==1) {
      chmin(f[i][1],f[i-1][1]+1);
      chmin(f[i][0],f[i-1][0]+3);
    } else {
      chmin(f[i][0],f[i-1][1]+1);
      chmin(f[i][1],f[i-1][0]+3);
    }
    //cout<<"DD "<<i<<" "<<s[i]<<" "<<f[i][0]<<" "<<f[i][1]<<endl;
  }
}

void work() {
  n=read(); scanf("%s",c+1);
  rep(i,1,n) if(c[i]=='1') s[i]=1; else s[i]=0;
  rep(x,0,1) rep(i,0,n+1) rep(y,0,1) f[x][i][y]=g[x][i][y]=inf;
  int l=1,r=n;
  while(l<=n&&s[l]==0) l++;
  while(r>=1&&s[r]==0) r--;
  if(l>n||r<1) {puts("0"); return;}
  dp2(f[0],l); reverse(s+1,s+n+1); dp2(g[0],n-r+1); reverse(g[0]+1,g[0]+n+1);
  reverse(s+1,s+n+1); rep(i,1,n) s[i]=1-s[i];
  dp1(f[1],l); reverse(s+1,s+n+1); dp1(g[1],n-r+1); reverse(g[1]+1,g[1]+n+1);
  reverse(s+1,s+n+1); rep(i,1,n) s[i]=1-s[i];
  int sum=0;
  //rep(i,1,n) cout<<f[0][i][1]<<" "; puts("");
  //cout<<"GG "; rep(i,1,n) cout<<g[0][i][0]<<" "; puts("");
  rep(i,1,n) {
    if(i<l) {
      if((l-i)&1) ans[i]=g[0][l][1]+2*(l-i)-1;
      else {
        int res1=g[0][l][0]+2*(l-i);
        int res2=2*(l-i)-1+(r-l)+g[1][l][0];
        ans[i]=min(res1,res2);
      }
    } else if(i>r) {
      if((i-r)&1) ans[i]=f[0][r][1]+2*(i-r)-1;
      else {
        int res1=f[0][r][0]+2*(i-r);
        int res2=2*(i-r)-1+(r-l)+f[1][r][0];
        ans[i]=min(res1,res2);
      }
    } else {
      int res11=i-l+f[1][i][1]+g[0][i][1];
      int res10=i-l+f[1][i][0]+g[0][i][0];
      int res21=r-i+g[1][i][1]+f[0][i][1];
      int res20=r-i+g[1][i][0]+f[0][i][0];
      //cout<<res11<<" "<<res10<<" "<<res21<<" "<<res20<<" "<<f[1][i][0]<<" "<<g[0][i][1]<<endl;
      ans[i]=min(min(res11,res10),min(res21,res20));
    }
    //cout<<i<<" "<<ans[i]<<endl;
    sum=(sum+ans[i]*i)%mod;
  }
  printf("%lld\n",sum);
}

signed main() {
  int T=read(); while(T--) work();
  return 0;
}